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

• dp[i][j]：从0到i号物品，容量上限为j的最大收益。
• dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]),取或者不取当前第i个物品。
• dp[i][0] = 0，容量为0收益为0,dp[0][j] = cost[j] or 0,当容量j大于第0个物品所需的容量时为cost[j].
• 按先i后j或者反过来都行，dp需要的都在上一层i靠左边的且已经更新了dp，不影响dp计算。

容量时反过来遍历的也可以，因为当前层的推导顺序不影响上一层，上一层已经算完了（二刷验证一下）。

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

    // 二维数组
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    // 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]);

        }
    }

    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}

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

来看dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，实际上i的使用就是为了让for循环当前层用的是上一层的结果，那么如果从后往前遍历j，那么上一层可以重复利用，直接拷贝到当前层，因为j前面的保存的还是上一层的结果，也就是滚动数组。

• 不能反过来，否则j用之前的时候这一层已经更新了就丢失了上一层的记录，相当于这个物品取了两次，遍历顺序也是先物品，再容量，否则每个容量只会装一个收益最高的物品（从后往前只取一个，前面都是0，那就是cost最大的）。
• dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]
• dp[j] = max(dp[j], dp[j - weight[i]] + value[i]).
• 初始化dp[j]都为0，先遍历物品，再倒序遍历容量。

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;
}

int main() {
    test_1_wei_bag_problem();
}

416. 分割等和子集

• 分两堆相等就考虑转化成找一堆是一半，进而转化成容量是j，最大收益（负重）尽可能也是j，如果存在容量是sum/2,最大收益也能达到sum/2,也就找到了答案，此题物品得到重量和收益是一样的。
• dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]，也就是尽可能往里面赛，转化成背包最大收益。
• 如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。
• 转化成1维01背包问题。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum /2;
        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]);
            }
        }
        if (dp[target] == target) return true;
        return false;
    }
};