416. 分割等和子集

416. 分割等和子集 - 力扣（LeetCode）

使用01背包解决

定义：物品种类=nums.size()，物品重量=i，背包大小=sum/2，判断能否刚好装满

  • 1 <= nums.length <= 200

  • 1 <= nums[i] <= 100

    根据题目条件，sum可直接去最大值200*100=20000，则背包大小可即为10000+1=10001

    dp[i]：

递推公式：

初始化：dp(10001,0)

遍历顺序：正常顺序

1
2
3
4
5
for(int i=0;i<nums.size();i++){
    for(int j=sum/2;j>=nums[i];j--){
        dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
    }
}

判断：即可

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int& i : nums)
            sum += i;
        if (sum % 2 != 0)
            return false;
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        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;
        else
            return false;
    }
};

1049.最后一块石头的重量II

1049. 最后一块石头的重量 II - 力扣（LeetCode）

和上题思路一样，相当于划分集合，使得两集合相最小

直接给出答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int& i : stones)
            sum += i;
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        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 - dp[target]*2;
    }
};

494.目标和

494. 目标和 - 力扣（LeetCode）

本题是装满有几种方法，是一个组合问题，常用公式如下：

1
dp[j] += dp[j - nums[i]]

思路：还是分两个集合，两者相减为target

left+right=sum

left-right=target

left=(sum+target)/2

right=(sum-target)/2

定义：dp[j] 表示：填满j的包有dp[j]种方法

递推公式：已知nums[i]，则凑成dp[j]就有dp[j - nums[i]] 种方法。

初始化：dp[0]=1

遍历顺序：先nums，后target

！注意的特殊情况，此时没有方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int& i : nums)
            sum += i;
        if (abs(target) > sum)
            return 0;
        if ((sum + target) % 2 != 0)
            return 0;
        int bagsize = (sum + target) / 2;
        vector<int> dp(bagsize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagsize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagsize];
    }
};

474.一和零

474. 一和零 - 力扣（LeetCode）

特殊点：每个物品有两个维度的重量

定义：：子集中i个0，j个1的最大长度

递推公式：计算str[i]中0、1个数记为m、n

初始化：

遍历顺序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    void func(string s, int& a, int& b) {
        a = b = 0;
        for (char i : s) {
            if (i == '0')
                a++;
            else
                b++;
        }
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        int a=0,b=0;
        for(int k=0;k<strs.size();k++){
            func(strs[k],a,b);
            for(int i=m;i>=a;i--){
                for(int j=n;j>=b;j--){
                    dp[i][j]=max(dp[i][j],dp[i-a][j-b]+1);
                }
            }
        }
        return dp[m][n];
    }
};