Question

Thief enters into the bank for robbery carrying a bag with 20KG capacity. He sees only 5 items with the following weights and values. In which order thief should pick items if he can take the fraction of any the items so that maximum gain can be achieved?

Items	1	2	3	4	5	6	7
Weight	3	17	7	6	15	5	10
Value	1	4	1	7	5	3	2

Answer 1

Here, fractional knapsack algorithm has to be performed on the given data.

The given data is :

Item	1	2	3	4	5	6	7
Weight	3	17	7	6	15	5	10
Value	1	4	1	7	5	3	2

Capacity given is 20 Kg.

The fractional knapsack algorithm is implemented using the following steps :

Step 1 :

Find the value / weight ratio of each item.

Let r = value / weight.

Then,

Item	1	2	3	4	5	6	7
Weight	3	17	7	6	15	5	10
Value	1	4	1	7	5	3	2
r	0.334	0.235	0.143	1.167	0.334	0.6	0.2

Step 2 :

Sort the items in non-increasing order of r value.

Item	4	6	1	5	2	7	3
Weight	6	5	3	15	17	10	7
Value	7	3	1	5	4	2	1
r	1.167	0.6	0.334	0.334	0.235	0.2	0.143

Initialize net value = 0

Step 3 :

Select the first item from the sorted list whose weight is less than or equal to the given capacity.

The item selected is Item 4.

Its weight is 6 Kg.

Its value is 7.

So, net value till now = old net value + value of item = 0 + 7 = 7 and the new capacity = Old capacity - weight of item = 20 Kg - 6 Kg = 14 Kg.

Step 4 :

Select the next item from the sorted list whose weight is less than or equal to the updated capacity.

The item selected is Item 6.

Its weight is 5 Kg.

Its value is 3.

So, net value till now = old net value + value of item = 7 + 3 = 10 and the new capacity = Old capacity - weight of item = 14 Kg - 5 Kg = 9 Kg.

Step 5 :

Select the next item from the sorted list whose weight is less than or equal to the updated capacity.

The item selected is Item 1.

Its weight is 3 Kg.

Its value is 1.

So, net value till now = old net value + value of item = 10 + 1 = 11 and the new capacity = Old capacity - weight of item = 9 Kg - 3 Kg = 6 Kg.

Step 6 :

Select the next item from the sorted list whose weight is less than or equal to the updated capacity.

Item 5 cannot be chosen as its weight exceeds the updated capacity.

But since fractional knapsack has to be used, a fraction of item 5 can be used.

Updated capacity = 6 Kg

15 kg of item 5 has value of 5.

Then, 6 kg of item 5 has value = ( 5 / 15 ) * 6 = 2.

So, net value till now = old net value + value of item = 11 + 2 = 13 and the new capacity = Old capacity - weight of item = 6 Kg - 6 Kg = 0 Kg.

The capacity is now 0 kg.

The required items are selected in the order :

Item 4, Item 6, Item 1, Item 5 of 6 kg.

Hence, the answer is :

Item 4, Item 6, Item 1, Item 5 of 6 kg.