做o2o平台网站需要多少钱,WDCP运行WordPress,网站 上一篇 下一篇,互联网项目推广方案Day41 动态规划第三天
LeetCode 416.分割等和子集
class Solution {
public:bool canPartition(vectorint nums) {int sum0;// dp[i]中的i表示背包内总和// 题目中说#xff1a;每个数组中的元素不会超过 100#xff0c;数组的大小不会超过 200// 总和不会大于…Day41 动态规划第三天
LeetCode 416.分割等和子集
class Solution {
public:bool canPartition(vectorint nums) {int sum0;// dp[i]中的i表示背包内总和// 题目中说每个数组中的元素不会超过 100数组的大小不会超过 200// 总和不会大于20000背包最大只需要其中一半所以10001大小就可以了vectorint dp(10001, 0);for(int i0; inums.size();i) {sumnums[i];}// 也可以使用库函数一步求和// int sum accumulate(nums.begin(), nums.end(), 0);if (sum%21) return false;int targetsum/2;// 开始 01背包for(int i0; inums.size();i) {for(int jtarget;jnums[i];j--) {dp[j]max(dp[j],dp[j-nums[i]]nums[i]);}}if (dp[target]target) return true;return false;}
};今天只有一道题整完再重新看一遍背包问题的详解。
