动态规划：01 背包问题详解

01 背包

有 n 件物品，与一次最多能背 w 重量的背包。第 i 件物品，重量为 weight[i]，得到的价值为 value[i]。

每件物品只能用一次，求解，将那些物品装入背包内，物品的价值总和最大。

	重量 (weight)	价值 (value)
物品 0	1	15
物品 1	3	20
物品 2	4	30

这是一个标准的背包问题。很多一看到这个，就直接想起用动态规划，而忽略了暴力解法。

这是因为没有自下而上思考的结果。

如下代码，一般动态规划问题，都是能通过回溯解决，因为每个物品都有两种可能（状态），被放入背包，或者不放入背包。

// 全局变量用于记录最大价值
int maxValue = 0;
// 物品的重量和价值数组
vector<int> weights = {1, 3, 4, 5, 6};
vector<int> values = {1, 3, 4, 5, 6};
// 背包容量
int capacity = 10;
// 回溯函数
void backtrack(int index, int currentWeight, int currentValue) {
    // 如果已经遍历完所有物品
    if (index == weights.size()) {
        // 更新最大价值
        if (currentValue > maxValue) {
            maxValue = currentValue;
        }
        return;
    }
    // 不选择当前物品 - 01 背包中的 0
    backtrack(index + 1, currentWeight, currentValue);
    // 选择当前物品 - 01 背包中的 1
    if (currentWeight + weights[index] <= capacity) {
        backtrack(index + 1, currentWeight + weights[index], currentValue + values[index]);
    }
}

如上的回溯算法，每个问题都有两个解法，通过暴力解决，但通常这种解法，是 O(2^n) 的时间复杂度，随着数量的增加呈指数级上升。

而动态规划仅仅需要 O(N*M) 就可以解决。

第一步：下标含义

dp[i][j] 表示将前 i 件物品装进限重为 j 的背包可以获得的最大价值，0<=i<=N, 0<=j<=W

第二步：推导公式

那么我们可以将 dp[0][0...W] 初始化为 0，表示将前 0 个物品 (即没有物品)，装入书包的最大价值为 0。那么当 i>0 时，dp[i][j] 有两种情况：

1. 不装入第 i 件物品，即 dp[i-1][j]；
2. 装入第 i 件物品（前提是能装下），即 dp[i-1][j-weight[i]]+value[i]。

第三步：书写代码

dp[weight.size()][bagweight + 1]; // weight 数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) 
            dp[i][j] = dp[i - 1][j];
        else 
            dp[i][j] = max(dp[i - 1][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])。

看到 dp[i][j] 与 dp[i-1][...] 的关系，可以发现，dp 都由上一行推导出来的 (也就是把 dp[i - 1] 那一层拷贝到 dp[i] 上)，所以可以压缩代码。

把二维数组，压缩为一维滚动数组。

这也就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

需要注意的是，为了防止上一层循环的 dp[0,...,j-1] 被覆盖，循环的时候 j 只能逆向枚举。

for(int i = 0; i < weight.size(); ++i){
    for(int j = bagWeight; j>=weight[i]; j--){
        dp[j] = max( dp[j], dp[j-weight[i]]+value[i] );
    }
}

相关题目

1、分割等和子集

给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

**示例 1：**输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]。

**示例 2：**输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int cur = 0;
        for(int i:nums) cur+=i;
        int sum = cur/2;
        if(sum*2 != cur) return false; // 意外情况，直接排除
        vector<int> dp(sum+1,0);
        for(int i=0; i<nums.size(); i++){
            for(int j=sum; j>=nums[i]; --j){
                dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        return sum==dp[sum]?true:false;
    }
};

2、最后一块石头的重量 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：**输入：stones = [31,26,33,21,40] 输出：5

核心思路是将石头分为两堆，使差值最小。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i : stones) sum+=i;
        int cur = sum;
        sum>>=1; // 右移 1 位，相当于除以 2
        vector<int> dp(sum+1, 0);
        for(int i=0; i<stones.size(); ++i){
            for(int j = sum; j>=stones[i]; --j){
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return cur-2*dp[sum];
    }
};

3、目标和

给你一个非负整数数组 nums 和一个整数 target。 向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数，可以构造一个表达式。 返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

**示例 1：**输入：nums = [1,1,1,1,1], target = 3 输出：5

**示例 2：**输入：nums = [1], target = 1 输出：1

本题本质是数学推导问题。设正数和为 P，负数和为 N，则 P+N=sum, P-N=target，推导出 P=(sum+target)/2。只要找到和为 P 的子集数量即可。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int cur = 0;
        for(int i:nums) cur+=i;
        int sum = (cur-target)>>1;
        if(sum*2!=cur-target||sum<0) return 0; // 直接就没有可能了
        vector<int> dp(sum+1);
        dp[0]=1; // 公式推导出来的正整数
        for(int i=0; i<nums.size(); ++i){
            for(int j=sum; j>=nums[i]; --j){
                dp[j]=dp[j-nums[i]]+dp[j];
            }
        }
        return dp[sum];
    }
};

4、一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n。 请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1。

**示例 1：**输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4

**示例 2：**输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(string str : strs){
            int num0=0,num1=0;
            for(char c : str){
                if(c=='0') num0++;
                else num1++;
            }
            for(int i=m; i>=num0; --i){
                for(int j=n; j>=num1; --j){
                    dp[i][j] = max(dp[i][j],dp[i-num0][j-num1]+1);
                }
            }
        }
        return dp[m][n];
    }
};