算法-背包问题

01背包问题
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); (j>=w[i])

一维化(由于递推关系i只和i-1 有关，可进行空间压缩，遍历j时需要逆序遍历)
for(int i=0;i<=n;i++){
for(int j=target;j>=w[i];j--){
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}

完全背包问题
商品不限量
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i], dp[i-1][j-2w[i]] + 2v[i], ... dp[i-1][j-kw[i]] + kv[i]); (j>=kw[i])
由于
dp[i][j-w[i]] = max(dp[i-1][j-w[i[], dp[i-1][j-2w[i]] + v[i], dp[i-1][j-3w[i]] + 2v[i], ... dp[i-1][j-(k+1)w[i]] + kv[i]);
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]);
一维化(由于递推关系i只和i-1 有关，可进行空间压缩，遍历j时可以正序遍历)
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

多重背包问题 （完全背包问题可以转换为多重背包问题k=j/w[i]）
商品限量k[i]个
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i], dp[i-1][j-2w[i]] + 2v[i], ... dp[i-1][j-kw[i]] + kv[i]); (k<k[i] && j>=kw[i])
for(int i=0;i<=n;i++){
for(int j=target;j>=w[i];j--){
for(int k=0;k <= k[i] && j >= kw[i];k++){
dp[j] = max(dp[j], dp[j-kw[i]] + kv[i]);
}
}
}