Question

the table is for 0-1 knapsack problem given for the following items, each labeled with weight and value. Assume the total weight limit W is 8 lbs.

Item	1	2	3	4
Value ($)	8	40	30	54
Weight (lb)	1	2	3	6

Solve the fractional knapsack problem using the input?

Answer 1

Greedy algorithm gives the optimal solution for Fractional knapsack problem if you select the object in decreasing order of the ratio Value/Weight. That is we select those object first which has maximum value of the ratio Value/Weight.

The Value/Weight ration for Item 1,2,3 and 4 is

Item	Value($)	Weight(lb)	Value/Weight
1	8	1	8
2	40	2	20
3	30	3	10
4	54	6	9

As the Value/Weight ratio is maximum for Item 2, we will select item 2 first, then item 3 and so on.

Weight limit W = 8lbs

W = 8lbs W = 8 - 1*2 = 6lbs (Item2) W = 6 - 1*3 = 3lbs (Item3) W = 3 - (1/2)*6 = 0lbs (Item4)

Profit = $0 Profit = 0 + 1*40 = $40 Profit = 40 + 1*30 = $70 Profit = 70 + (1/2)*54 = $97

The selected items will be (0, 1, 1, 1/2) and profit is $97.

If you're still having any doubt then please feel free to ask in the comment section.