Leetcode题解动态规划01背包（1）：问题简介

有一个容量为 N 的背包&＃xff0c;要用这个背包装下物品的价值最大&＃xff0c;这些物品有两个属性&＃xff1a;体积 w 和价值 v。

定义一个二维数组 dp 存储最大价值&＃xff0c;其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w&＃xff0c;价值为 v&＃xff0c;根据第 i 件物品是否添加到背包中&＃xff0c;可以分两种情况讨论&＃xff1a;

• 第 i 件物品没添加到背包&＃xff0c;总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值&＃xff0c;dp[i][j] &＃61; dp[i-1][j]。
• 第 i 件物品添加到背包中&＃xff0c;dp[i][j] &＃61; dp[i-1][j-w] &＃43; v。

第 i 件物品可添加也可以不添加&＃xff0c;取决于哪种情况下最大价值更大。因此&＃xff0c;0-1 背包的状态转移方程为&＃xff1a;

dp[i][j] &＃61; value dp[i - 1][j - w] &＃43; v;

public int knapsack(int W, int N, int[] weights, int[] values) {int[][] dp &＃61; new int[N &＃43; 1][W &＃43; 1];for (int i &＃61; 1; i <&＃61; N; i&＃43;&＃43;) {int w &＃61; weights[i - 1], v &＃61; values[i - 1];for (int j &＃61; 1; j <&＃61; W; j&＃43;&＃43;) {if (j >&＃61; w) {dp[i][j] &＃61; Math.max(dp[i - 1][j], dp[i - 1][j - w] &＃43; v);} else {dp[i][j] &＃61; dp[i - 1][j];}}}return dp[N][W];
}

public int knapsack(int W, int N, int[] weights, int[] values){int[][] dp &＃61; new int[N&＃43;1][W&＃43;1];for(int i&＃61; 1; i<&＃61;N; i&＃43;&＃43;){int w &＃61; weights[i-1], v&＃61; vlaues[i-1];for(int j&＃61;1; j<&＃61;W; j&＃43;&＃43;){if(j >&＃61; w){dp[i][j] &＃61; Math.max(dp[i-1][j], dp[i-1][j-w] &＃43; v);elsedp[i][j] &＃61; dp[i-1][j];}}}return dp[N][W];
}

空间优化

在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道&＃xff0c;前 i 件物品的状态仅与前 i-1 件物品的状态有关&＃xff0c;因此可以将 dp 定义为一维数组&＃xff0c;其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时&＃xff0c;

因为 dp[j-w] 表示 dp[i-1][j-w]&＃xff0c;因此不能先求 dp[i][j-w]&＃xff0c;以防将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]&＃xff0c;在程序实现时需要按倒序来循环求解。

public int knapsack(int W, int N, int[] weights, int[] values) {int[] dp &＃61; new int[W &＃43; 1];for (int i &＃61; 1; i <&＃61; N; i&＃43;&＃43;) {int w &＃61; weights[i - 1], v &＃61; values[i - 1];for (int j &＃61; W; j >&＃61; 1; j--) {if (j >&＃61; w) {dp[j] &＃61; Math.max(dp[j], dp[j - w] &＃43; v);}}}return dp[W];
}

public int knapsack(int W, int N, int[] weights, int[] values){int[] dp &＃61; new int[W&＃43;1];for(int i&＃61;1; i<&＃61;N; i&＃43;&＃43;){int w &＃61; weights[i-1], v&＃61; values[i-1];for(int j&＃61;W; j>&＃61;1; j--){if(j >&＃61; w)dp[j] &＃61; Math.max(dp[j], dp[j-w] &＃43; v);}}
}

无法使用贪心算法的解释

0-1 背包问题无法使用贪心算法来求解&＃xff0c;也就是说不能按照先添加性价比最高的物品来达到最优&＃xff0c;这是因为这种方式可能造成背包空间的浪费&＃xff0c;从而无法达到最优。考虑下面的物品和一个容量为 5 的背包&＃xff0c;如果先添加物品 0 再添加物品 1&＃xff0c;那么只能存放的价值为 16&＃xff0c;浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2&＃xff0c;价值为 22.

变种

• 完全背包&＃xff1a;物品数量为无限个

• 多重背包&＃xff1a;物品数量有限制

• 多维费用背包&＃xff1a;物品不仅有重量&＃xff0c;还有体积&＃xff0c;同时考虑这两种限制

• 其它&＃xff1a;物品之间相互约束或者依赖