1、0-1背包问题

价值V，重量W，任一物品只有一件,总共n件物品,容量为m

// 递推式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
// dp[i][j] 代表可选择前i件物品，重量小于等于j的最大价值
// 由于之和i-1有关，可以降为一维求解,倒序使得小的没更新
for(int i=1; i<=n; i++) {
    for(int j=m; j>=w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
    }
}

2、 完全背包问题

任一物品有无限件

// 递推式： dp[i][j] = max(dp[i][j],dp[i][j-w[i] + v[i])
//依然可以降为一维，顺序使得小的都更新了
for(int i=1; i<=n; i++) {
    for(int j=w[i]; j<=m; j++) {
        dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
    }
}

3、多重背包问题

物品i有c[i]件

// dp[j] = max{dp[j], dp[j−k∗a[i]]+k∗b[i]}  1<=k<=c[i]
for(int i=1; i<=n; i++) {
    for(int j=m; j>=w[i]; j--) {
        for(int k=0; k<=c[i] && k*w[i]<j; k++) {
            dp[j] = Math.max(dp[j], dp[j-k*w[i]] + k*v[i]);       
        }
    }
}

4、混合背包问题

以上问题混合时

for(int i=1; i<=n; i++) {
    if(i是0-1背包)
        0-1背包问题方法
    else if(i 是完全背包)
        完全背包问题方法
    else if(i 是多重背包)
        多重背包问题方法
}