Question

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

a.	60
	b.	100
	c.	80
	d.	70

Answer 1

Solution:

Here given {value,weight} pairs {{40,20},{30,10},{20,5}} and knapsack size is 25.

	P1	P2	P3
value	40	30	20
weight	20	10	5
value/weight	2	3	4

Now sort the value/weight values in ascending order and fill the bag with each pair weight one by one.

So after arranging value/weights in ascending order it looks like P3,P2,P1.

Now Bag Size = 25

Contents in Bag	Remaining Bag Size	Profit	Total Profit
P3 = 5	25-5=20	20	20
P2 = 10	20-10 = 10	30	50
P3=10	10-10=0	10*2=20	70

After filling 10 from p3 bag size becomes zero so the total profit was 20+30+20=70.

So option D is correct i.e 70. Here weights are divisible.

Note: If you have any queries please post a comment before giving any review thanks a lot..always available to help you..