代码随想录训练营Day31:动态规划3：0-1背包

1.0-1背包基础

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

1.1动态规划五部曲

1. 确定dp数组以及下标的含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。在后续的程序中都是默认背包的容量为i，物品的类别为j，保证统一。

2.确定递推公式

• 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
• 放物品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] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.初始化：需要根据具体的进行具体的初始化

4.那么问题来了，先遍历 物品还是先遍历背包重量呢？

其实都可以！！ 但是先遍历物品更好理解。对于先遍历物品再遍历容量，简称为组合问题：这种情况下的遍历物品的顺序是一个固定的。

// 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数组）。这种可以称之为排列问题可能会出现相同的结果但是不同的排列方式

例如这样：

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

5.举例：跳过，直接看下面的代码

2.416分割等和子集

第一种方法：动态规划的方法

理论分析：首先要分割成等和的子集，要满足的第一个条件就是其累加和能被2整除。

动态规划五部曲

1.dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。

2.递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);//分为填不添加这个数情况下的最大累加和。二维状态下是：dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])：i表示物品j表示容量

3.初始化：首先初始化的长度为target+1,因为我们只需要找到一个容量为sum一半的能够全部装满就代表还存在另外一部分。

4.确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！因为这样可以避免重复存放。可以看到上面的二维的递推公式，首先遍历的是物品，其次遍历的是容量，如果内部的容量是正序，那么会出现一个物品被多次使用。比如有1 2；2 3（重量 价值）的物品，这样的情况，正序遍历出现的结果就是dp数组为[2,4]而不是[2,3]的情况了。

class Solution {
public:
    //动态规划的方法
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int n = nums.size();
        for(int i = 0;i<n;i++){
            sum += nums[i];
        }
        if(sum%2 ==1)return false;
        int target = sum/2;
        vector<int> dp(1+target,0);//生成一个dp数组
        for(int i = 0;i<n;i++){
            for(int j = target;j>=nums[i];j--){
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);//分加不加的情况下的最大值
            }
        }
        if(dp[target] == target)return true;
        return false;
 
    }
};

3.最后一块石头的重量

首先就是分析题意：我该如何让最后的石头的重量最小呢？就是通过将其分成两部分，两部分的差值越小那么对应的最后能够得到的重量也就越小。那么将其化成一个背包问题就是在求容量为target下能够存放的最大的重量为多少即0-1背包问题。

动态规划五部曲

1.dp[j]：容量为j时候的最大价值（重量）。

2.递推公式：dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);//在这个里面重量和价值都是用stones[i]来表示的，所以得到上述的公式，具体可以参考前面这一题的思路。

3.初始化：首先来说的话我们要用sum来确定总重量，然后确定dp数组的空间，应该生成的vector<int> dp(1+sum/2,0)的，但是按照题目给定了最多只有3000个，所以可以直接创建一个大的空间（1500>sum/2）。

4.循环的遍历方向：参照前面的分割等和子集。如果是一维的需要怎样的操作。

注意事项：最后返回的是 return sum - 2*dp[target];因为此时分成的两部分的重量分别为sum -dp[target]和dp[target]，且必定是target>=dp[target]所以最后返回的是两者的差值即可。

class Solution {
public:
    //dp数组，求得是能够背得的最大的重量，使用这种方法，巧妙的将碰撞的减法问题给反向思考为一个加法问题，最后相减来确定最小的重量
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(1501,0);
        int sum = accumulate(stones.begin(),stones.end(),0);//求累加和
        int target = sum/2;
        for(int i = 0; i<stones.size();i++){
            for(int j = target;j>=stones[i];j--){
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum - 2*dp[target];
    }
};

4.494目标和

结题思路看下面的注释部分。

动态规划五部曲：

1.dp[j]:代表容量为j的最大价值（和）的组合数。

2.递推公式：dp[j] += dp[j-nums[i]];组合类问题就是对应的多个的累加和。

3.初始化：在这个地方初始化需要初始化的长度是dp(avg+1);而不需要sum+1，因为left = avg;

4.遍历顺序：对于组合问题：应该先遍历背包再遍历容器。再就是遍历方向的问题：里面那个是从大往小的进行遍历，同前面一样是为了避免重复的情况。参考分割等和子集问题。

class Solution {
public:
    //在这个里面，left代表的是正数的部分，right代表的是负数的部分
    //left + right = sum(定值)
    //left - right = target(定值)
    //left = (sum + target)/2;//所以此时两者的累加和一定能被2整除才行。
    //还需要考虑的就是sum>=abs(target)不然无法保证能够完成累加到指定的为止
    //所以此时dp[i]表示的就是累加和为i的个数
    //dp[j] += dp[j - nums[i]];//每一个nums[i]都对应的一个dp[j - nums[i]]种方法可以累加到这里
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        
        int sum = accumulate(nums.begin(),nums.end(),0);//求和,后面那个应该是初始化的赋值
        if(abs(target)>sum)return 0;
        if((target+sum)%2==1) return 0;
        int avg = (target+sum)/2;
        vector<int> dp(avg+1);
        dp[0] = 1;
        for(int i = 0;i<nums.size();i++){
            for(int j = avg;j>= nums[i];j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[avg];
    }
};

5.474一和零

1.dp[i][j]:i表示0的个数，j表示1的个数。dp[i][j]表示当前容量下的最大的个数。

2.递推公式： dp[i][j] = max(dp[i][j],dp[i-zeros][j-ones]+1);//其中dp[i-zeros][j-ones]表示的是dp[j-weight[i]]的意思，1:表示value[i].

3.初始化：默认开始的时候都是0。

4.遍历顺序：反序遍历保证不重复。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));//生成一个dp数组，用于确定有i个1，j个0
        for(auto str:strs){
            int zeros = 0;
            int ones = 0;
            for(auto st:str){
                if(st == '0'){
                    zeros++;
                }else{
                    ones++;
                }
            }
            for(int i = m;i >=zeros;i--){
                for(int j = n;j>=ones;j--){
                    dp[i][j] = max(dp[i][j],dp[i-zeros][j-ones]+1);
                }
            }
        }
        return dp[m][n];
    }
};