文章目录

• 前言 01背包
• 一、二维dp数组01背包
• • 1.1 确定dp数组以及下标的含义
  • 1.2 确定递推公式
  • 1.3 初始化
  • 1.4 遍历顺序
  • 1.5推导dp数组
  • 1.6 完整代码
• 二、一维dp数组01背包（滚动数组）
• • 2.1 确定dp数组以及下标的含义
  • 2.2 确定递推公式
  • 2.3 初始化
  • 2.4 遍历顺序（重要）
  • 2.5推导dp数组
  • 2.6 完整代码
• 总结

前言 01背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

来源：链接: linkand链接: link

一、二维dp数组01背包

1.1 确定dp数组以及下标的含义

dp[i][j]表示从下标为 0—i 的物品中，放进容量为j的背包，价值总和最大是多少。

1.2 确定递推公式

可以有两个方向推出dp[i][j]

• 不放物品i：也就是说当前物品的重量weight[i]> 背包容量j 时，物品无法放入背包，所以背包中的价值依然和之前相同 dp[i][j] = dp[i-1][j];
• 放物品i：也就是说，当前的背包容量j是可以满足当前物品的重量，没有放入物品i之前的背包最大价值为 dp[i-1][j-weight[i]]；放入物品i 背包得到的最大价值就变为dp[i-1][j-weight[i]]+value[i]；

dp[i][j] = max( dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);

1.3 初始化

如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

for (int j = 0 ; j < weight[0]; j++) {dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

其实从递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。

1.4 遍历顺序

有两个遍历的维度：物品与背包重量

先遍历 物品还是先遍历背包重量呢？

先遍历物品，再遍历背包的过程如图所示：

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.length; i++) { // 遍历物品for(int j = 1; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

先遍历背包，再遍历物品：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量for(int i = 1; i < weight.length; i++) { // 遍历物品if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

都可以，因为正如上边所说 数值推导是由左上方来的

虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，不会影响dp[i][j]公式的推导！

1.5推导dp数组

1.6 完整代码

public class BagProblem {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数组// 创建数组后，其中默认的值就是0for (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");}}
}

二、一维dp数组01背包（滚动数组）

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了dp[j]

需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

2.1 确定dp数组以及下标的含义

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2.2 确定递推公式

此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，相当于 二维dp数组中的dp[i-1][j- weight[i]] + value[i]，即放物品i，一定是取最大的，毕竟是求最大价值，

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

2.3 初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

2.4 遍历顺序（重要）

for(int i = 0; i < weight.length; i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
倒序遍历的原因：是为了保证物品i只被放入一次。

• 问题一：为什么倒序遍历？

举例：
物品0的重量weight[0] = 1，价值value[0] = 15
正序遍历：dp[0] = 0;
dp[1] = Math.max(dp[1], dp[1-weight[0]]+value[0]) = 15; （dp数组已经都初始化为0）
dp[2] = Math.max(dp[2] , dp[2-weight[0]]+value[0]) = 30; （dp数组已经都初始化为0）
也就是说物品0又被放进去一次，所以不能正序遍历。

为什么倒序遍历可以？
倒序遍历：先求dp[2]
dp[2] = Math.max(dp[2] , dp[2-weight[0]]+value[0]) = 15; （dp数组已经都初始化为0）
dp[1] = Math.max(dp[1], dp[1-weight[0]]+value[0]) = 15; （dp数组已经都初始化为0）

• 问题二：为什么二维dp数组历的时候不用倒序？
  因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

• 问题三：可不可以先遍历背包容量嵌套遍历物品呢？
  不可以
  如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

2.5推导dp数组

2.6 完整代码

    public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWight = 4;testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(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] + " ");}}

总结

使用一维dp数组的写法，比较直观简洁，而且空间复杂度还降了一个数量级！