Loading... ## 前言 背包问题: 给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。 问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? ## 背包算法 用二维数组 dp[i][j] ,表示在面对前i个物品,且背包容量为j时所能获得的最大价值。 | 物品 | 重量 | 价值 | | --- | --- | --- | | a | 1 | 3 | | b | 2 | 5 | | c | 3 | 6 | | 物品 i \ 背包容量 j| 0 | 1 | 2 | 3 | 4 | 5 | 6 | | --- | --- | --- | --| --- | --- | --- | ----| | a (i = 2) | 0 | 3 | 3 | 3 | 3 | 3 | 3 | | b (i = 2) | 0 | 3 | 5 | 8 | 8 | 8 | 8 | | c (i = 3) | 0 | 3 | 5 | 8 | 9 | 11 | 14 | 整个表格是从左到右,从上到下生成的。 重要推导过程: 我们来提取部分值的生成来一探究竟。 #### dp[3][4] 当 i = 3 即物品栏中有了c这个可选项; 当 j = 4 即背包容量为4 . 此时的总价值如何计算呢? 选择1 : 不考虑新添加的物品。 此时 总价值 对应 i = 2 , j = 4 也就是 dp[2][4] 即等于8. 选择2: 考虑将新添加的物品放进去,此时由于新添加的物品会占用一定的空间。 总价值: dp[3][4 - 新物品的重量] +新物品的价值。即 dp[3][4-3] + 6 = 9. 通过比较选择1和选择2即可得到最大价值为9. #### dp[3][5] 选择1: dp[3][5] = dp[2][5] = 8 选择2: dp[3][5] = dp[3][ 5 - 3] + 6 = 11 所以 dp[3][5] = 11. #### dp[3][6] 选择1: dp[3][6] = dp[2][6] = 8 选择2: dp[3][6] = dp[3][6 - 3] + 6 = 14 所以 dp[3][6] = 14. ## 代码实例 ```java /** * 求最大背包装载价值 * 每个物品只有一个,只能装一次。(01背包) * * 例如: * 重量 价值 * a 1 3 * b 2 5 * c 3 6 * * 背包最大重量 6 * * 求 最大价值 */ public class Solution { public int getMaxValue(int[][] items, int maxWeight){ if (items == null || items.length == 0){ return 0; } int itemNum = items.length; // 新建dp表 int[][] dp = new int[itemNum][maxWeight + 1]; for (int i = 0; i < maxWeight + 1; i++) { if (items[0][0] <= i){ dp[0][i] = items[0][1]; } } for (int i = 1; i < itemNum; i++) { for (int j = 0; j < maxWeight + 1; j++) { // 先复制为上一行的 dp[i][j] = dp[i - 1][j]; if (j >= items[i][0]){ dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - items[i][0]] + items[i][1]); } } } return dp[itemNum - 1][maxWeight]; } @Test void test(){ System.out.println(getMaxValue(new int[][]{{1, 3}, {2, 5}, {3, 6}}, 6)); } } ``` 最后修改:2020 年 09 月 15 日 11 : 51 AM © 允许规范转载