背包问题模型

n个物品
物品体积v[i] 1-n
物品价值w[i] 1-n

在体积不超过S的前提下，求最大价值

定义+属性+状态转移
dp[i][j]定义：在只考虑前i个物品的情况下，体积不超过j的最大价值
属性：最大
状态转移：dp[i-1][] -> dp[i][]的转移方式只分为：选第i个物品和不选第i个物品两种方式

0-1背包：每个物品只能选一次

dp[0]=0
for(int i=1; i<=n; i++) {
    for(int j=S; j>=w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
    }
}

ans = dp[S]

完全背包：每个物品能选无数次

dp[0]=0
for(int i=1; i<=n; i++) {
    for(int j=0; j<=S; j++) {
        dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
    }
}

ans = dp[S]

注意v[i],w[i]都是从1开始表示，因为dp[0][0]表示前0个物品中体积不超过0的，也是合法状态，需要留出来