Question

Find the optimal solution for knapsack instance \[ n=3,\quad m=20, \] \[ (p_1,p_2,p_3)=(25,24,15) \] and \[ (w_1,w_2,w_3)=(18,15,10). \]

• A. \((0,\frac{2}{3},1)\)
• B. \((\frac{1}{2},\frac{1}{3},\frac{1}{4})\)
• C. \((0,1,\frac{1}{2})\)
• D. \((1,1,1)\)

Hint:

For Fractional Knapsack: \[ \text{Select items in decreasing order of } \frac{\text{Profit}}{\text{Weight}}. \] This greedy strategy always produces the optimal solution.

Answer 1

The Correct Option is A