0-1 Knapsack Problem

Problem:  Given a knapsack that can hold at most W weight items, also given a list of items with their weight wi and value vi (no items share the same weight), try to find a valid assignment which achieve the highest value in the knapsack (can't  be over-weighted at the same time).

Solution: We can use DP to solve this problem. However, one-dimension DP is not enough. If we only record state s[0], s[1], ... s[W], the later state may not be able to reuse previous states. Instead, we need a two-dimension DP here:

• First sort the items based on their weights
• The status we want to calculate is s[i, w], which means if the total weight is w and we can only use up To the ith item (based on weight and non-descending), the optimal maximum value we can get.
•  s[0, w] = 0 and  s[i, 0] = 0. 
• For  s[i, w], if wi > w,  s[i, w] =  s[i-1, w]; otherwise,  s[i, w] = max ( s[i-1, w], s[i-1, w-wi] + vi).