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.
1
votes
2 Answers
7
votes
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.
1
votes
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.
