Why dynamic programming for 0/1 Knapsack?

Question

I looked at many resources and also this question, but am still confused why we need Dynamic Programming to solve 0/1 knapsack?

The question is: I have N items, each item with value Vi, and each item has weight Wi. We have a bag of total weight W. How to select items to get best total of values over limitation of weight.

I am confused with the dynamic programming approach: why not just calculate the fraction of (value / weight) for each item and select the item with best fraction which has less weight than remaining weight in bag?

Answer 1

For your fraction-based approach you can easily find a counterexample.

Consider

W=[3, 3, 5]
V=[4, 4, 7]
Wmax=6

Your approach gives optimal value Vopt=7 (we're taking the last item since 7/5 > 4/3), but taking the first two items gives us Vopt=8.

Answer 2

As other answers pointed out, there are edge cases with your approach.

To explain the recursive solution a bit better, and perhaps to understand it better I suggest you approach it with this reasoning:

For each "subsack"

1. If we have no fitting element there is no best element
2. If we only have one fitting element, the best choice is that element
3. If we have more than one fitting element, we take each element and calculate the best fit for its "subsack". The best choice is the highest valued element/subsack combination.

This algorithm works because it spans all the possible combinations of fitting elements and finds the one with the highest value.

A direct solution, instead, is not possible as the problem is NP-hard.

Answer 3

Just look at this counterexample:

Weight 7, W/V pairs (3/10),(4/12),(5/21)

Answer 4

Greedy algorithm fails when there is unit ratio case. for example consider the following example:

n= 1 2, P= 4 18, W= 2 18, P/W= 2 1

Knapsack capacity=18

According to greedy algorithm it will consider the first item since it's P/W ratio is greater and hence the total profit will be 4 (since it cannot insert the second item after first as the capacity reduces to 16 after inserting the first item).

But the actual answer is 18.

Hence there are multiple corner cases where greedy fails to give optimal solution, that's why we use Dynamic programming in 0/1 knapsack problem.