1.前提：什么是0-1背包
🤓情况描述：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态，取或者不取。
举一个例子，之后我们将拿这里例子进行后续分析
weight = []1,3,4]
value = [15,20,30]
| 物品 | weight | value |
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
2.实现：二维dp讲解
💯动态规划五部曲：
1.（重要）首先搞懂dp[i][j]代表的意思： 代表从0-i个物品中，取出任意个，放入容量为j的背包的价值总和。i表示取的物品，j表示背包容量
2.确定递推公式：
分为两个方向思考价值：一个是不放i物品，一个是放了i物品。
如果容量不满足：直接将上一个背包价值赋值给dp[i][j]
如果容量满足：
不放i物品价值，那么dp[i][j]就是未放i物品的价值，即dp[i-1][j]
放了i物品价值，那么此时最大价值：dp[i][j]应该是dp[i-1][j-weight[i]+value[i]]
两者取最大值比较即可
递推公式为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.初始化dp数组：
如下图所示：
当背包容量为0的时候，所有价值为0；当i=0时，只有一个物品可供选择，所以物品0行值为15；之后当选择多起来之后，可以根据递推公式得出此时物品的价值。所以初始化dp[i][0]和dp[0][j]即可满足初始化条件，供我们后续计算物品价值。同时对于其他值，我们给初始化成0，这样我们在后续进行求最大值的时候不会对我们产生影响
| 背包种类/背包容量 | 0 | 1 | 2 | 3 | 4 |
| 物品0 | 0 | 15 | 15 | 15 | 15 |
| 物品1 | 0 | 0 | 0 | 0 | 0 |
| 物品2 | 0 | 0 | 0 | 0 | 0 |
代码实现：
// 创建dp数组 int goods = weight.length; // 获取物品的数量 //这里数组容量为什么要+1呢？ //因为我们又添加了一个0，容量变成了5，此时size才为4，求n的时候，保证不越界，使求的n就是dp[i][n]，加一保证不越界和好使用 int[][] dp = new int[goods][bagSize + 1]; // 初始化dp数组 // 创建数组后，其中默认的值就是0 //为什么这里是以weight[0]作为其实值呢？，当只有一个物品时候， //要从容量符合的位置开始装，初始化第一行价值 for (int j = weight[0]; j <= bagSize; j++) { dp[0][j] = value[0]; }
4.确定遍历顺序： 因为dp数组需要知道之前的物品价值，才能求得价值最大值，所以遍历顺序是从前向后。
5.举例推导： 就以我们上面的例子来进行推导
代码实现：二维dp模板
package excrise.算法专训.背包问题; public class 背包问题0_1 { public static void main(String[] args) { int[] weight = {1,3,4}; int[] value = {15,20,30}; int bagSize = 4; testWeightBagProblem(weight,value,bagSize); } /** * 动态规划获得结果 * @param weight 物品的重量 * @param value 物品的价值 * @param bagSize 背包的容量 */ public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){ // 创建dp数组 int goods = weight.length; // 获取物品的数量 int[][] dp = new int[goods][bagSize + 1]; // 初始化dp数组 // 创建数组后，其中默认的值就是0 for (int j = weight[0]; j <= bagSize; j++) { dp[0][j] = value[0]; } // 填充dp数组 for (int i = 1; i < weight.length; i++) { for (int j = 1; j <= bagSize; j++) { if (j < weight[i]) { /** * 当前背包的容量都没有当前物品i大的时候，是不放物品i的 * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值 */ dp[i][j] = dp[i-1][j]; } else { /** * 当前背包的容量可以放下物品i * 那么此时分两种情况： * 1、不放物品i * 2、放物品i * 比较这两种情况下，哪种背包中物品的最大价值最大 */ dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]); } } } // 打印dp数组 for (int i = 0; i < goods; i++) { for (int j = 0; j <= bagSize; j++) { System.out.print(dp[i][j] + "\t"); } System.out.println("\n"); } } }
总结： 对于背包求价值那块，两层for循环换位置当你有些迷糊时，要时刻去回顾dp[i][j]代表的含义是什么，慢慢才能理解进去。
3.实现：一维dp讲解（滚动数组）
相对于二维dp，我们更加常用一维dp来解决背包问题。
1.理解dp{j】的含义： 相对于二维dp[i][j]，一维dp[j]中的j表示的是二维数组中的背包容量j，dp[j]表示此时背包的最大价值
2.确定地推公式
分为两个方向思考价值：一个是不放i物品，一个是放了i物品。
如果容量不满足：直接将上一个背包价值赋值给dp[j]
如果容量满足：
不放i物品价值，那么dp[i][j]就是未放i物品的价值，即dp[j] (dp[j]是滚动更新的，所以可以写成dp[j])
放了i物品价值，那么此时最大价值：dp[j]应该是dp[j-weight[i]+value[i]]
两者取最大值比较即可
递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 滚动更新
3.初始化dp数组
数组初始化为0，即定义之后就会默认为0；原因在第四步讲解
4.遍历顺序
因为题中要求的是，每个物品只能使用一次。如果从前向后计算的话，那么同一个物品会被使用多次，即放了多次。所以对于一维数组来说，只能从后往前进行计算。这样才满足同一个物品使用一次的条件。从后往前的话，因为每个物品的值初始化时0，所以保证了只使用一次。
5.举例推导：
依旧使用上面的例子：
| 背包种类/背包容量 | 0 | 1 | 2 | 3 | 4 |
| 物品0 | 0 | 15 | 15 | 15 | 15 |
| 物品1 | 0 | 0 | 0 | 0 | 0 |
| 物品2 | 0 | 0 | 0 | 0 | 0 |
代码实现：
package excrise.算法专训.背包问题; public class 背包问题0_1一维数组 { public static void main(String[] args) { int[] weight = {1, 3, 4}; int[] value = {15, 20, 30}; int bagWight = 4; test(weight, value, bagWight); } public static void test(int[] weight, int[] value, int bagWeight){ int wLen = weight.length; //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值 int[] dp = new int[bagWeight + 1]; //遍历顺序：先遍历物品，再遍历背包容量 for (int i = 0; i < wLen; i++){ for (int j = bagWeight; j >= weight[i]; j--){ dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } //打印dp数组 for (int j = 0; j <= bagWeight; j++){ System.out.print(dp[j] + " "); } } }
