动态规划-背包问题

什么是背包问题

背包问题是动态规划很经典的问题，他有很多的变种，但是万变不离其宗。背包问题最根本的特点就是有一个目标（填满背包）和一堆物品（nums[i]），看看是否能够通过选取部分物品（nums[i]）来满足目标（填满背包）。
目标可能是题目直接给出，也可能是要我们自己推测出来。

面试要掌握的背包类型有以下两种：
1、0/1背包问题：每个元素最多选取一次
2、完全背包问题：每个元素可以重复选择

01背包问题

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

假设有4件物品，重量和价值如下：

  • 物品1：重量1kg，价值15元
  • 物品2：重量3kg，价值20元
  • 物品3：重量4kg，价值30元
  • 物品4：重量5kg，价值50元

背包最大承重为8kg。

步骤1：确定dp数组及下标的含义

dp[i][j]表示考虑到第i件物品时，背包重量不超过j时的最大价值。

步骤2：确定递推公式

对于dp[i][j]，有两个方向来得到它：
如果选择第i件物品，dp[i][j] = dp[i-1][j-weight[i]] + value[i]；如果不选择，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-weight[i]]：这是在考虑前 i-1 个物品时，背包承重限制为 j-weight[i] 的情况下的最大价值。换句话说，这代表在留出足够空间放入第 i 个物品之前的最大价值。
dp[i][j] = dp[i-1][j]：沿用了在没有第 i 个物品的情况下，即 i-1 个物品的最大价值。

步骤3：dp数组如何初始化

  • dp[0][j]：当只有第一个物品可选时，如果背包容量 j 大于等于第一个物品的重量，则初始化为第一个物品的价值，否则为0。
  • dp[i][0]：对于任何物品，如果背包容量为0，那么初始化为0，因为没有容量来装任何物品。

步骤4：确定遍历顺序

先遍历物品，然后遍历背包容量和先遍历背包容量，再遍历物品，都是可以的。本质是因为dp[i][j]是由dp[i-1][j]和dp[i-1][j-weight[i]]得到的，所以要想得到dp[i][j]必须保证它上面一格，和它左上的内容都已经生成，而两种遍历方式都可以达到这个目标。

例子分析

我们使用上述物品和背包容量构建dp表：

1
2
3
4
5
6
	  背包重量  ->     0   1   2   3   4   5   6   7   8
                    +----------------------------------
物品 0 (1kg, 15元) |   0  15  15  15  15  15  15  15  15
物品 1 (3kg, 20元) |   0  15  15  20  35  35  35  35  35
物品 2 (4kg, 30元) |   0  15  15  20  35  45  45  50  65
物品 3 (5kg, 50元) |   0  15  15  20  35  50  65  65  70

让我们以dp[3][5]为例。这表示考虑前3件物品，背包容量为5kg时的最大价值。我们在这里有两个选择：

  1. 不选择物品3，此时价值为dp[2][5] = 45。
  2. 选择物品3，此时价值为物品3的价值加上剩余空间（0kg）的最大价值，即value[3] + dp[2][0] = 0 + 50 = 50。

因此，dp[3][5] = max(45, 50) = 50。

通过这种方法，我们可以填充整个dp表，并在dp[3][8]中找到最大价值，即背包最多能装入的物品的最大价值。在这个例子中，最大价值是70元。

由于dp[i][j]是由dp[i-1][j],dp[i-1][j-stones[i]]得到的，这两个全部来自dp[i-1][]也就是上一行，那么我们可以用一维数组收集结果，即dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
但是注意我们不能再从背包容量小到大来遍历了，为什么呢，因为我们dp[i][j]需要它上面一格和左上的一格数据。如下表，但是当我们使用一行数组进行记录的时候，第二列的15由于之前算过被覆盖为20，那么这时本来是35，就变成了40，也就是物品1被放了两次进去，所以为了避免这个情况，我们要按背包容量从大到小来遍历。因为dp[j]右侧先算，所以它左侧的数据dp[j - stones[i]]不会被“污染”，就可以得到正确的结果。

1
2
3
4
5
6
	  背包重量  ->     0   1   2   3   4   5   6   7   8
                    +----------------------------------
物品 0 (1kg, 15元) |   0  15  15 [15] 15  15 [15] 15  15
物品 1 (3kg, 20元) |   0  15  15  20  35  35 [35] 35  35
物品 2 (4kg, 30元) |   0  15  15  20  35  45  45  50  65
物品 3 (5kg, 50元) |   0  15  15  20  35  50  65  65  70

尝试解决背包问题

1049. 最后一块石头的重量 II

方法一：

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]
输出：5

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {  
    public int lastStoneWeightII(int[] stones) {  
        int sum = 0;  
        for (int stone : stones) {  
            sum += stone;  
        }  
        int target = sum / 2;  
        int[][] dp = new int[stones.length][target + 1];  
//        for (int i = 0; i < stones.length; i++) { //dp[i][0]默认初始化为0  
//            dp[i][0]=0;  
//        }  
        for (int j = stones[0]; j <= target; j++) {  
            dp[0][j] = stones[0];  
        }  
        for (int i = 1; i < stones.length; i++) {  
            for (int j = 1; j <= target; j++) {  
                if (j >= stones[i]) {  
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);  
  
                } else dp[i][j] = dp[i - 1][j];  
            }  
        }  
        return sum - 2 * dp[stones.length - 1][target];  
  
    }  
}```

**在计算target的时候，`target = sum / 2` 因为是向下取整，所以`sum - dp[target]` 一定是大于等于`dp[target]`的**。

那么相撞之后剩下的最小石头重量就是` (sum - dp[target]) - dp[target]`。


方法二：

这道题我们发现`dp[i][j]`是由`dp[i-1][j],dp[i-1][j-stones[i]]`得到的，这两个全部来自`dp[i-1][]`也就是上一行，那么我们可以用一维数组收集结果。注意这里要从背包容量从大到小的顺序遍历，这样能保证不重复选取同一个石头。

```java
class Solution {  
    public int lastStoneWeightII(int[] stones) {  
        int sum = 0;  
        for (int stone : stones) {  
            sum += stone;  
        }  
        int target = sum / 2;  
        int[] dp = new int[target + 1];  
//        for (int i = 0; i < stones.length; i++) { //dp[i][0]默认初始化为0  
//            dp[i][0]=0;  
//        }  
        for (int j = stones[0]; j <= target; j++) {  
            dp[j] = stones[0];  
        }  
        for (int i = 1; i < stones.length; i++) {  
            for (int j = target; j > 0; j--) {  
                if (j >= stones[i]) {  
                    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);  
  
                }//else dp[j]=dp[j];  
            }  
        }  
        return sum - 2 * dp[target];  
  
    }  
}