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

Concept:
• The fractional knapsack problem aims to maximize the total value in a knapsack with limited capacity, where we can take fractions of items.
• Unlike the 0/1 knapsack problem (which requires Dynamic Programming), the fractional version can be solved optimally using a Greedy approach.

Step 1: Identify the optimal greedy strategy
To maximize profit per unit of space occupied, we should prioritize items that give the most value for every kilogram of weight they add.
This metric is the "value density" or the value-to-weight ratio: \(V_i / W_i\).

Step 2: Outline the algorithm

• Calculate the ratio \(V_i / W_i\) for every item.
• Sort the items in descending order of this ratio.
• Add the highest ratio items into the knapsack first.
• If an item cannot fit completely, take a fraction of it to fill the remaining capacity.

Step 3: Evaluation
Picking based on pure value or pure weight alone is not guaranteed to be optimal. The ratio captures the relative worth of the item compared to the space it consumes.