Q:

Why dynamic programming for 0/1 Knapsack?

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?

A:

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.

