背包问题之0-1背包问题
问题描述：有n个物品，第 i 个物品的重量与价值分别为 w[i]w[i]w[i] 与 v[i]v[i]v[i]。背包容量为 V，试问在每个物品最多使用一次（物品必须保持完整）的情况下，如何让背包装入的物品具有更大的价值总和。现有数据如下：
w = [2,3,4,5];
v = [3,4,5,6];
V = 8;
解题思路：令 dp[i][j]dp[i][j]dp[i][j] 表示容量为 j 时放入前 i 个物品的最大价值。对于第 i 件物品，有两种选择，即放或者不放。若不放，则 dp[i][j]=dp[i−1][j]dp[i][j]=dp[i-1][j]dp[i][j]=dp[i−1][j]；如放，则 dp[i][j]=dp[i−1][j−w[i]]+v[i]dp[i][j]=dp[i-1][j-w[i]]+v[i]dp[i][j]=dp[i−1][j−w[i]]+v[i]。因此有 dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])。
public int knapsackProblem(int[] w, int[] v, int cap) {
int[][] dp = new int[w.length + 1][cap + 1];
for (int i = 1; i = 1; j--) {
if (w[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[w.length][cap];
}
时间复杂度与空间复杂度均为 O(nV)O(nV)O(nV)。
空间优化：由以上可知，迭代过程中的第 i 行仅与前一行相关，因此可以将存储空间可被压缩成一维数组，即 dp[j]=max{dp[j],dp[j−w[i]]+v[i]}dp[j]=max\{dp[j],dp[j-w[i]]+v[i]\}dp[j]=max{dp[j],dp[j−w[i]]+v[i]}。由于 dp[j−w[i]]dp[j-w[i]]dp[j−w[i]] 表示的是上一行容量小于 j 的值，为了避免数据被覆盖，需从后往前进行计算。
public int knapsackProblem(int[] w, int[] v, int cap) {
int[] dp = new int[cap + 1];
for (int i = 0; i = w[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
return dp[cap];
}
上一篇：背包问题之分数背包问题
下一篇：背包问题之完全背包问题
作者：Z o n g
