Question

Consider the following greedy algorithm for the knapsack problem: each time we pick the item with the highest value to weight ratio to the bag. Skip items that will make the total weight exceeded the capacity of the bag. Find a counterexample to show that this approach will not work, and the result could be 100 times worse than the optimal solution. That is, construct a table of set of items with weight and values and find a bag capacity value, such that, this approach picks a set of items of total value W to put in bag, while it is possible to pick items that are of value >= 100W.

Answer 1

Weight : 1 1000     20 30 40 9

Values: 10 9000    10 10 10 1

Capacity of knapsack = 1000

Consider the above weight value pair. I've sorted according to value by weight ratio. If we use 0/1 knapsack approach, we would get Profit = 9000 because we will pick second item i.e. weight = 1000.

If we use greedy fractional knapsack approach, we still get profit 10+(999/1000)*9000 = 9001

In your greedy approach, we select first item, capacity become 999 so we can't select second item so skip it. Now we have capacity to select all items so take them. Total profit = 10 + 10 + 10 + 10 + 1 = 41 = W

we can see that 9000> 200*W. So in this example, your greedy approach fail.

There are examples in which selecting more value/weight ratio item can result in poor solution like the above.