一、01 backpack problem

Given:

• Value array v = {8, 10, 6, 3, 7, 2}
• Weight array w = {4, 6, 2, 2, 5, 1}
• Knapsack capacity c = 12

Solution analysis

1. Two-dimensional DP

m[i,j] : The largest value in the set of values with volume <=j from the first i items