代码随想录算法训练营第四十一天|01背包问题， 01背包问题—— 滚动数组，分割等和子集

01背包问题，你该了解这些！ 

题目链接：46. 携带研究材料（第六期模拟笔试） (kamacoder.com)

思路：第一次遇到背包问题，好好记住吧。代码随想录 (programmercarl.com)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m,n;
    cin>>m>>n;
    vector<int>z(m);
    vector<int>value(m);
    for(int i=0;i<m;i++){
        cin>>z[i];
    }
    for(int i=0;i<m;i++){
        cin>>value[i];
    }
    
    vector<vector<int>> dp(m,vector<int>(n+1,0));
    for(int i=z[0];i<=n;i++){
        dp[0][i]=value[0];
    }
    
    for(int i=1;i<m;i++){
        for(int j=0;j<=n;j++){
            if(j<z[i])dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-z[i]]+value[i]);
            
        }
    }
    cout<<dp[m-1][n];
}

01背包问题，你该了解这些！ 滚动数组  

滚动数组，说白了就是将上一题中的二维数组压缩成一维数组。dp数组的更新方式变为dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

但有一点需要注意，这里我直接引用官网原文：

这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

为什么呢？

倒序遍历是为了保证物品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

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

同时，只能先遍历物品，嵌套倒序遍历背包容量，不能反着来。

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    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]);
        }
    }
    cout << dp[bagWeight] << endl;
}

分割等和子集 

题目链接：416. 分割等和子集 - 力扣（LeetCode）

思路：首先来看我最初的思路，先将数组排序，然后设一个堆栈来记录我选择了哪些元素。从小到大遍历数组，同时累加压入堆栈的元素，如果累加值过大于目标值，则将栈顶弹出同时继续尝试加入该元素，否则更新累加值并加入堆栈（注意此时可以return的情况）。实际上，这是一种贪心解法，并不能解决这个问题，具体来说，是因为下一个元素并不能决定这个元素是否该留在这个堆栈中，而是该元素之后的所有元素共同决定这个元素能否留在堆栈中（这应该就是贪心和DP的区别所在吧）。下面是错误做法的核心部分（与前文略有差异，该做法从大到小遍历数组）：

        r.push(nums.back());
        int z = nums.size() - 1;
        while (!z) {
            for (int j = z; j >= 0; j--) {
                if (sum - nums[j] > 0) {
                    sum -= nums[j];
                    r.push(nums[j]);
                } else if (sum - nums[j] < 0 && (!r.empty())) {
                    r.pop();
                    j++;
                } else if ((sum - nums[j]) == 0) {
                    return true;
                }
            }
            z--;
        }

该方法不能在走投无路的时回溯到错误还没有发生的时刻，也就不能解决问题。不得不说，这道题让我对贪心和DP的理解更加深入了。

正确做法如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        // 也可以使用库函数一步求和
        // int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};