动态规划05-等和子集

发布时间:2023年12月25日

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

思路分析

将题目信息翻译一下,就是从原集合中选取数据元素,使得和是总和的一半,对于每一个数据元素,只有选中和没有选中两种可能,所以本题就是01背包的变体。

  1. 确定dp[j]的含义,那就是当需要数据总和为j的时候,实际能够实现的数据总和。
  2. 确定迭代的顺序,dp[j]有两种情况,第一种是遍历到当前下标的数据的时候,要添加当前的数据,那么就是dp[j-1]+value[i];第二种情况就是不添加当前数据,那么最终的结果就是dp[j-1]。
  3. dp数组初始化,dp[0]=0,然后所有其他的初始化为0就可以
  4. 确定遍历顺序,按照数组的顺序·从前往后遍历
  5. 带入验证

代码解析

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说:每个数组中的元素不会超过 100,数组的大小不会超过 200
        // 总和不会大于20000,背包最大只需要其中一半,所以10001大小就可以了
        vector<int> 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]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};
文章来源:https://blog.csdn.net/weixin_73074012/article/details/135210787
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。