Question

5) (10 pts) Greedy Algorithms The 0-1 Knapsack problem is as follows: you are given a list of items, each item has an integer weight and integer value. The goal of the problem is to choose a subset of the items which have a sum of weights less than or equal to a given W with a maximal sum of values. For example, if we had the following five items (each in the form (weight, value)): 11(6, 13), 2(4, 10), I3(1, 1), 14(8, 12), and 15(5, 9) and W 13, then our maximal achievable value is 13 + 10 + 1 = 24. corresponding to the subset containing the first three items, which weigh 11 units, which is less than or equal to our weight limit of 13 units. A proposed greedy algorithm to solve the problem is as follows: (1) sort the items by per unit value. Go through the list of items in this order, taking each item as long as there is room to do so. (For this example, when we sort by per unit value, the ordering would be 12, 11, 15, 14, and 13. Then, we'd take 12, followed by 11. Skip 15 and 14 because enough weight wasn't left, then take I3.) This algorithm is incorrect. Create a single example (a set of items with weights and values) for which this algorithm fails. In your example, show what answer the algorithm will produce and show a subset that is more valuable (but also within the weight limit.)

Answer 1

Consider I1(6,13), I2(4,10), I3(3,15), I4(2,10), I5(1,10)
and W = 13
Sorting the items by per unit value i.e., value / weight
I5,I3,I4,I2,I1
Consider subset (I5,I3,I4,I2)
weight: 1 + 3 + 2 + 4 = 10
values: 10 + 15 + 10 + 10 = 45
But in this case if we consider the subset (I5,I3,I4,I1)
weight: 1 + 3 + 2 + 6 = 12
values: 10 + 15 + 10 + 13 = 48
We can get more value with in the given weight. If we consider the other subset.
Hence the algorithm is wrong.