巴南区网站建设,站内推广的方法,江苏省建设银行网站,快速排名程序题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
思路分析
将题目信息翻译一下#xff0c;就是从原集合中选取数据元素#xff0c;使得和…题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
思路分析
将题目信息翻译一下就是从原集合中选取数据元素使得和是总和的一半对于每一个数据元素只有选中和没有选中两种可能所以本题就是01背包的变体。
确定dp[j]的含义那就是当需要数据总和为j的时候实际能够实现的数据总和。确定迭代的顺序dp[j]有两种情况第一种是遍历到当前下标的数据的时候要添加当前的数据那么就是dp[j-1]value[i]第二种情况就是不添加当前数据那么最终的结果就是dp[j-1]。dp数组初始化dp[0]0然后所有其他的初始化为0就可以确定遍历顺序按照数组的顺序·从前往后遍历带入验证
代码解析
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;// dp[i]中的i表示背包内总和// 题目中说每个数组中的元素不会超过 100数组的大小不会超过 200// 总和不会大于20000背包最大只需要其中一半所以10001大小就可以了vectorint dp(10001, 0);for (int i 0; i nums.size(); i) {sum nums[i];}// 也可以使用库函数一步求和// int sum accumulate(nums.begin(), nums.end(), 0);if (sum % 2 1) return false;int target sum / 2;// 开始 01背包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]);}}// 集合中的元素正好可以凑成总和targetif (dp[target] target) return true;return false;}
};
