**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*i*th 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 w*i > w,*s[*i*,*w*] = s[*i-1*,*w*]; otherwise, s[*i*,*w*] = max ( s[*i-1*,*w*], s[*i-1, w-wi*] +*vi*).

## No comments:

## Post a Comment