Question

Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.

(a) 60

(b) 80

(c) 100

(d) 40

The question was posed to me in an internship interview.

I want to ask this question from Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II

Answer 1

Correct answer is (a) 60

Easiest explanation - The value/weight ratio are-{2,3,4}. So we include the second and third items wholly into the knapsack. This leaves only 5 units of volume for the first item. So we include the first item partially.

Final value = 20+30+(40/4)=60.