动态规划之01背包问题解题方法

01背包是背包问题的理论基础，完全背包也是经过01背包演变而来的。LeetCode上没有纯01背包的问题，都是01背包应用方面的题目，也就是需要将其转化为01背包问题。所以，记录一下从代码随想录-01背包理论基础学习到纯01背包问题的解题方法，具体应用题需要靠自己来将其转化成01背包，dp数组状态转移方程、初始化可能会和纯01背包问题有一些不同，需要具体问题具体分析。

概念

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

例子

背包最大重量为4，物品的重量和价值如下：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

解题方法

动规五部曲

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

使用二维数组，dp[i][j]数组表示从前i个物品中任意取，放进容量为j的背包中所得到的物品的最大价值。

2.递推公式(状态转移方程式)

对于每个物品来说有两种选择，不选取或选取。所以dp[i][j]可以从这两类选择中推导出：

• 不选取物品i：

  由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，即dp[i][j] = dp[i - 1][j]。

• 选取物品i：

  由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]]表示背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i]（物品i的价值） ，就是背包放物品i得到的最大价值，即dp[i][j] = dp[i - 1][j - weight[i]] + value[i]。

所以，递推公式为：

• 如果物品i的重量大于背包容量j时，背包放不下，就不能选择物品i，dp[i][j] = dp[i - 1][j]；
• 如果物品i的重量小于等于背包容量j时，dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。

3.dp数组的初始化

关于初始化，一定要和dp数组的定义一致。

两种初始化情况：

• 背包容量j为0，不管选择哪些物品，所得到的物品最大价值一定为0，所以dp[i][0] = 0；
• 物品数量为0时，不论背包容量多大，所得到的物品最大价值一定为0，所以dp[0][j] = 0。

dp[i][j](物品\背包)	0	1	2	3	4
无物品	0	0	0	0	0
物品0	0
物品1	0
物品2	0

4.dp数组的遍历顺序

有两个遍历的维度：物品和背包，那么问题来了，先遍历物品还是先遍历背包重量呢？

其实都可以，因为递推公式为dp[i][j] = dp[i - 1][j]和dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])这两种情况，不论哪种，dp[i - 1][j]和dp[i - 1][j - weight[i]]都在dp[i][j]的左上角方向，而两种遍历顺序都能够获取到dp[i][j]左上角方向的值，先遍历物品会更好理解。

• 先遍历物品再遍历背包，代码如下

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况，n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) { // 遍历物品
    for (int j = 0; j <= n; j++) { // 遍历背包
        if (j < weight[i - 1]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
        }
    }
}

• 先遍历背包再遍历物品，代码如下

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况，n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
for (int j = 0; j <= n; j++) { // 遍历背包
    for (int i = 1; i <= m; i++) { // 遍历物品
        if (j < weight[i - 1]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
        }
    }
}

5.打印dp数组

dp数组对应值如下：

dp[i][j](物品\背包)	0	1	2	3	4
无物品	0	0	0	0	0
物品0(重量1，价值15)	0	15	15	15	15
物品1(重量3，价值20)	0	15	15	20	35
物品2(重量4，价值30)	0	15	15	20	35

完整代码

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况，n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
// dp[i][0]和dp[0][j]情况的初始化省略，因为dp数组的默认值就是0
for (int i = 1; i <= m; i++) { // 遍历物品
    for (int j = 0; j <= n; j++) { // 遍历背包
        if (j < weight[i - 1]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
        }
    }
}
return dp[m][n];

优化为一维dp数组

由于递推公式中dp[i][j]都是用到了dp[i - 1]即上一层的数据，所以可以将dp[i][j]优化为dp[j]。

dp数组以及下标的含义

这里dp[j]数组的表示容量为j的背包中所得到的物品的最大价值。

递推公式(状态转移方程式)

递推公式变为dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])。

dp数组的初始化

dp[0] = 0即可

dp数组的遍历顺序

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
    // 注意这里遍历背包顺序变成了倒序，很重要
    for (int j = n; j >= weight[i - 1]; j--) {
        dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
    }
}

为什么这里背包从大到小倒序遍历？

倒序遍历是为了保证物品i只被放入一次！如果一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15，如果正序遍历，dp[1] = dp[1 - weight[0]] + value[0] = 15，dp[2] = dp[2 - weight[0]] + value[0] = 30，此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

倒序就是先算dp[2]，dp[2] = dp[2 - weight[0]] + value[0] = 15（dp数组已经都初始化为0），dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

为什么二维dp数组历的时候不用倒序呢？

因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖。

这里可不可以先遍历背包容量嵌套遍历物品呢？

不可以！因为一维dp的写法，背包容量一定是要倒序遍历，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即背包里只放入了一个物品。

打印dp数组

略

一维数组完整代码

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
    // 注意这里遍历背包顺序变成了倒序，很重要
    for (int j = n; j >= weight[i - 1]; j--) {
        dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
    }
}
return dp[n];