# Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.

+1 vote
Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.

(a) 100, 80

(b) 110, 70

(c) 130, 110

(d) 110, 80

I got this question in an online quiz.

Question is taken from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II

+1 vote
by (962k points)
selected by

Correct option is (d) 110, 80

The best I can explain: Assuming items to be divisible-

The value/weight ratio are {3, 2, 4}.So we include third and first items wholly. So, now only 15 units of volume are left for second item. So we include it partially.

Final volume = 20+60+50x(15/25)=80+30=110

Assuming items to be indivisible- In this case we will have to leave one item due to insufficient capacity.

Final volume = 60 + 20 = 80.

+1 vote
+1 vote
+1 vote
+1 vote