Is there any greedy algorithm that would give an optimal solution to non-fractional(0-1 Knapsack) Knapsack problem? I know that there is one for the fractional version of Knapsack giving the optimal solution.
There are no greedy algorithms for 0-1 Knapsack even though greedy works for Fractional Knapsack.
This is because in 0-1 Knapsack you either take ALL of the item or you don't take the item at all, unlike in Fractional Knapsack where you can just take part of an item if your bag overflows. This is crucial.
Here is an example that disproves that Greedy Algorithm works for 0-1 Knapsack. Let's say that you have a bag of size 6 and these items:
Item Value Size Value/Size
A 5.5 4 1.38
B 4 3 1.33
C 4 3 1.33
For 0-1 Knapsack, if you tried to be greedy you would always take the item that has the highest Value/Size, which is Item A. After taking Item A, you only have room for an item of size 2 or less so you wouldn't be able to pick up anything else. That means that the only thing you have in your bag is Item A which is a total value of 22.
On the other hand, if you had not been greedy and taken the most valuable item and had instead taken Item B, then you would have enough room to take Item C as well. This would have resulted in a total value of 24 in the bag, which is better than the greedy route.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With