Cases where the greedy algorithm fails the 0-1 knapsack p‌r‌o‌b‌l‌e‌m

Question

I'm looking for a case where the greedy algorithm of picking items of the highest value/weight ratio that has weight < max weight and putting it in the knapsack first won't work. Does anyone have examples? Because otherwise, the worst case for greedy would be O(nlogn) (nlogn to sort in descending value/weight and n to go through it) while the dynamic programming way's worst case would be O(nW), making greedy faster when logn < W.

Answer 1

Consider a backpack with capacity 4, and items with the following weights and values:

Item  Weight  Value  value/Weight
 A      3      1.65     0.55
 B      2      1        0.5
 C      2      1        0.5

A greedy algorithm based on value per weight would first choose item A and then quit, there being insufficient capacity left for any other item -- total value 1.65. The optimal solution, however, is to choose items B and C, which together exactly take up the full capacity and have a combined value of 2.

More generally, the greedy algorithm can fail when it chooses a set of items that don't take up the whole available capacity. A different set of items that fills more of the available capacity will sometimes be a better choice.

Answer 2

We can also generalize the cases where the greedy algorithm fails to give a globally optimal solution.

It is as follows

weights = {1, x, x+1} target weight = z

• x is a multiple of z
• y is less than z and greater than x
• both x and y are greater than 1
• included 1 as to have a solution in all cases for greedy approach

For the above general case, most of the time the greedy approach fails. You can try out examples.