1、区别
0-1背包问题描述：
对于 n 个物品，有体积 v 和价值 w，在背包总量为 C 的情况下，怎么选物品才能使得背包里装的东西价值最大？
我们通常的解法是，定义一个 dp[i][j]，对于前 i 个物品，当背包容量为 j 的情况下，可以使得物品价值最大。所以对于每一个物品 i，有可选和不选两个选项。不选时，在当前背包容量为 j 的情况，直接继承前 i - 1 个物品选择的价值，即 dp[i][j] = dp[i - 1][j]；选择物品 i 时，那么在其物品价值为 w[i] 的基础上，再使用剩下的 j - v[i] 的容量装下前 i - 1 个物品，即 dp[i][j] = dp[i - 1][j - v[i]] + w[i]。那么一个0-1背包的问题就解决了。
public int maxValue(int N, int C, int[] v, int[] w) {
int[][] dp = new int[N][C+1];
// 先处理「考虑第一件物品」的情况
for (int i = 0; i <= C; i++) {
dp[0][i] = i >= v[0] ? w[0] : 0;
}
// 再处理「考虑其余物品」的情况
for (int i = 1; i < N; i++) {
for (int j = 0; j < C + 1; j++) {
// 不选该物品
if(j - v[i] < 0){
dp[i][j] = dp[i-1][j];
}else{
// 选择该物品，前提「剩余容量」大于等于「物品体积」
dp[i][j] = dp[i-1][j-v[i]] + w[i];
}
}
}
return dp[N-1][C];
}
对于0-1背包问题，我们发现当前 dp[i][j] 只与上一层 i - 1 想关联，所以我们可以使用 dp[2][N] 来定义 dp 数组，使得状态压缩；后面再把状态压缩到一维，但是对于内层循环要倒序遍历，要不然会导致新值覆盖原来的值。一般状态压缩技巧性比较强，如果没有特别熟练的情况下，暂时不推荐。
完全背包的描述：
对于 n 类物品，每类物品的数量时无限的，有体积 v 和价值 w，在背包总量为 C 的情况下，怎么选物品才能使得背包里装的东西价值最大？
此时对于每类物品来说，数量时无限的，可以无限去选。我们可以复用0-1背包的解法，定义 dp[i][j]，只不过含义变成了对于前 i 类物品，在容量为 j 的情况下怎么选使得价值最大。
那么对于每类物品 i，我可以选0件，则为 dp[i - 1][j - 0 * v[i]] + 0 * w[i] = dp[i - 1][j]；选1件，则为 dp[i - 1][j - v[i]] + w[i]；选2件，则为 dp[i - 1][j - 2 * v[i]] + 2 * w[i]；选 k 件，则为 dp[i - 1][j - k * v[i]] + k * w[i]。则 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], ..., dp[i - 1][j - k * v[i]] + k * w[i])。我们可以编码为：
/**
* dp[i][j] = Math.max(dp[i - 1][j] 选0，选1，直到选 k，如果 j - v[k] < 0 则退出}
*/
public int maxValue(int N, int C, int[] volume, int[] worth){
int[][] dp = new int[N][C + 1];
for(int i = 0; i <= C; i++){
// 显然当只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件
int max = i / volume[0];
dp[0][i] = max * worth[0];
}
for(int i = 1; i < N; i++){
for(int j = 0; j <= C; j++){
int max = 0;
for(int k = 0; ; k++){
if(j - k * volume[i] < 0){
break;
}
max = Math.max(max, dp[i - 1][j - k * volume[i]] + k * worth[i]);
}
dp[i][j] = max;
}
}
return dp[N - 1][C];
}
然后，此种朴素的解法是三层 for 循环，效率较低，可以将公式化简为这样（自己手推一下，很简单）：
化简过程
然后代码就可以写成这样：
public int maxValue(int N, int C, int[] volume, int[] worth){
int[][] dp = new int[N][C + 1];
for(int i = 0; i <= C; i++){
// 显然当只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件
int max = i / volume[0];
dp[0][i] = max * worth[0];
}
for(int i = 1; i < N; i++){
for(int j = 0; j <= C; j++){
if(j - volume[i] < 0){
dp[i][j] = dp[i - 1][j];
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - volume[i]] + worth[i]);
}
}
}
return dp[N - 1][C];
}
网友评论