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.