发布广东建设工程信息网站,广州网站建设乛新科送推广,漳州北京网站建设公司哪家好,抖音开放平台目标和
题目
给一个都是正整数的组合#xff0c;然后你可以在里面任意添加或-#xff0c;求使得最后结果为
目标和S#xff08;target#xff09;的有多少种方法#xff1f;
范围
数组非空#xff0c;且长度不会超过 20 。初始的数组的和不会超过 1000 。保证返回的…目标和
题目
给一个都是正整数的组合然后你可以在里面任意添加或-求使得最后结果为
目标和Starget的有多少种方法
范围
数组非空且长度不会超过 20 。初始的数组的和不会超过 1000 。保证返回的最终结果能被 32 位整数存下。
思路
用背包方法的话这是怎么带入背包方法的任意添加或-后会分成两个组合
是left总和-是right总和如果结果为目标和target的话sumleftright(总和)targetleft-right(目标和)推出rightleft-target 推出sumleftleft-target最后推出 lefttargetsum/2利用target和sum都确定这一点可以求出的组合left来。
带入背包问题
假设加法的总和为xleft那么减法对应的总和就是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个数方法不同的方法就不考虑放还是不放了都放进去然后累加起来。比如
已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包。已经有一个2nums[i] 的话有 dp[3]种方法 凑成 容量为5的背包。已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包已经有一个5 nums[i]的话有 dp[0]中方法 凑成 容量为5的背包他们的dp[1-5]种方法都加起来。
初始化
dp[0]1为什么不知道按定义来容量为0的背包的最大方法数为10和-0是一种方法吗总之dp[0]1能通过
总代码
class Solution {
public:int findTargetSumWays(vectorint 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;vectorint 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背包的操作区别不过这里有01两个维度而已。
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
vectorvectorint dp(m 1, vectorint (n 1, 0));
遍历顺序
一维度的01背包都是后续遍历这里虽然像两维度的但却是两个相同维度的一维度所以顺序先遍历那边都行我是这样理解的。
总代码
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0)); // 默认初始化0for (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];}
};
这题也蛮抽象的
