Question

In the fractional knapsack problem, the greedy choice is based on ($i^{th}$ item has worth/value as $V_i$ and weight as $W_i$) :

• A. Maximum value ($V_i$)
• B. Minimum weight ($W_i$)
• C. Maximum value/weight ($V_i/W_i$) ratio
• D. Random choice

Hint:

Always think of "Value per kg." If Gold is \$60/g and Silver is \$1/g, you pick the Gold first because its $V/W$ ratio is higher.

Answer 1

The Correct Option is C

The Fractional Knapsack problem is a classic optimization problem that can be solved using a Greedy strategy. 1. Understanding the Problem: Unlike the 0/1 Knapsack problem where you must take an entire item or none at all, the fractional version allows you to take parts of an item. To maximize total value while staying under a weight limit, you want to pick items that give you the "most bang for your buck." 2. Evaluating Greedy Criteria:
• Greedy by Value: Taking the most expensive items first might fill the bag with very heavy items, leaving no room for other valuable goods.
• Greedy by Weight: Taking the lightest items fills the bag with potentially worthless items.
• Greedy by Ratio ($V_i/W_i$): This calculates the value per unit of weight. By picking the items with the highest "density" of value, you ensure that every gram added to the knapsack contributes the maximum possible profit. 3. Conclusion: The optimal greedy choice is to sort items in decreasing order of their Value-to-Weight ratio ($V_i/W_i$) and fill the knapsack accordingly.