动态规划,01背包问题
题目是这样的:
给定一个正整数数组,问能否将其分为两个子数组,使得这两个子数组的和相等,也即是否存在一个子数组的和为为总和的一半
例如:数组{1,2,3,3,4,5},...总和为18,子数组{1,2,3,3}和为9,剩下的{4,5}和也为9,所以可以成功划分
思想和上一篇【你的的背包,让我走的好缓慢】思想差不多,假设和为w,对于dp[w]表示能否划分为和为w的数组,对于每个元素...,可以选择加入子数组或者不加入子数组,所以dp方程可以写为dp[j]=dp[j] || dp[j-nums[i]]
整个代码可以这样写:
#include
#include <vector...accumulate(nums.begin(), nums.end(), 0);
sum = sum / 2;
cout << canPartition(nums, sum);
}
其实这道题和力扣上的...计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。你可以认为每种硬币的数量是无限的。