494.目标和 474.一和零

目标和

题目

给一个都是正整数的组合，然后你可以在里面任意添加+或-，求使得最后结果为

目标和S（target）的有多少种方法？

范围

• 数组非空，且长度不会超过 20 。
• 初始的数组的和不会超过 1000 。
• 保证返回的最终结果能被 32 位整数存下。

思路

用背包方法的话，这是怎么带入背包方法的？任意添加+或-后会分成两个组合

+是left（总和），-是right（总和），如果结果为目标和target的话，sum=left+right(总和)，target=left-right(目标和)，推出right=left-target 推出sum=left+（left-target）最后推出 left=（target+sum）/2，利用target和sum都确定这一点，可以求出+的组合left来。

带入背包问题

假设加法的总和为x（left），那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为，装满容量为x的背包，有几种方法。

这个时候装满了容量为x的背包相当于，任意+或者-之后的目标值被满足了。

这里如果x = (target + sum) / 2没有被整除，说明最后目标值不能为target，说明没有方案

同时如果 S的绝对值大于sum，那么也没有方案

递推公式

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

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法，nums[i]是那个都是正整数的组合的第i个数，方法不同的方法就不考虑放还是不放了，都放进去，然后累加起来。比如

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包
• 他们的dp[1-5]种方法都加起来。

初始化

dp[0]=1，为什么？不知道，按定义来，容量为0的背包的最大方法数为1，+0和-0是一种方法吗？总之dp[0]=1能通过

总代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + sum) / 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];
    }
};

这题也挺抽象的

一和零

题目

给一个元素只由0和1组成的集合strs，再给两个正整数m和n，要求找出最多有m个0和n个1的集合strs的子集，同时这个子集的元素最多。

示例 ：

• 输入：strs = ["10", "0", "1"], m = 1, n = 1
• 输出：2
• 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

思路

带入背包问题，相当于把strs的每个元素作为物品，每个物品计算他们的0和1的数量，然后执行放和不放最多承载m个0和n个1背包的操作，区别不过这里有0，1两个维度而已。

m 和 n 和 元素最多的子集 是3个维度，用二维数组dp[i][j]，意思是最多m个0和n个1的集合的最大元素个数是dp[i][j]，然后套用01背包公式求出结果就行了。

递推公式

dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

由01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])得来，

zeroNum oneNum相当于之前的重量weight[i]，dp[i][j]和dp[i - zeroNum][j - oneNum]的意思还是放入还是不放入的意思，不过由之前只有 j 的一个维度变成了 i 和 j 的两个维度，加1是相当于之前的价值value[i]，因为每次遍历的是单个字符串，所以只能+1.

初始化

物品价值不会为负数，初始化为0

vectorint>> dp(m + 1, vector<int> (n + 1, 0));

遍历顺序

一维度的01背包都是后续遍历，这里虽然像两维度的，但却是两个相同维度的一维度，所以顺序先遍历那边都行，我是这样理解的。

总代码

class Solution {
public:
    int findMaxForm(vector& strs, int m, int n) {
        vectorint>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
 
        for (string str : strs) { // 遍历每个物品，也就是每个字符串
            int oneNum = 0, zeroNum = 0;
 
            for (char c : str) {//遍历当前物品也就是当前的字符串的0和1数量
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            //用上面得到当前字符串的0和1数量
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
 
        }//注意第一个for到这里才结束
 
        return dp[m][n];
 
    }
};

这题也蛮抽象的