算法打卡 Day43（动态规划）-背包问题 + 分割等和子集

0-1 背包问题理论基础

0-1 背包一般的题目要求是给定不同重量不同价值的物品，每个物品只有一个，已知背包中最大的负重，求在此限制条件下背包中的最大价值。

dp[i][j]表示表示重量为[0,i]的背包任取放入容量为 j 的背包中，对于每个物品，我们可以讨论放与不放物品 i 的情况，如果放物品 i，则当前价值为 dp[i-1][j]，如果放物品 i，则价值为 dp[i-1][j-weight[i]]+value[i]

0-1 背包问题滚动数组

可以将上一标题下的二维 dp 数组进行压缩，对于背包重量为 j 的情况，直接原位对上一行进行修改，就能压缩为一维数组。这样递推公式变为 dp[j] = max(dp[j-1], dp[j-weight[i]]+value[i])。在遍历顺序上必须采用倒序遍历。

Leetcode 416-分割等和子集

题目描述

https://leetcode.cn/problems/partition-equal-subset-sum/description/

解题思路

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