分割等和子集

题目

将给定的物品，装满一半容量的箱子。

具体思路

1. 首先计算背包的容量大小，如果背包不能被2整除，那么说明背包是不能够被分成两组的，直接返回 false 就行。
2. 背包的容量设置为 space/2 ，如果不能实现，那么不能装满。

具体实现

class Solution {
    public boolean canPartition(int[] nums) {
        int space = 0;
        for (int i = 0; i < nums.length; i++) {
            space += nums[i];
        }
        // 不能整除肯定不能分开成两组相同大小的
        if (space % 2 == 1) {
            return false;
        }

        space /= 2;
        int[] dp = new int[space + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = space; j > 0; j--) {
                if (j - nums[i] >= 0) {
                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }
        }
        return dp[space] == space ? true : false;
    }
}

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int target = 0;
        for (int i = 0; i < nums.size(); i++) {
            target += nums[i];
        }
        if (target % 2 == 1)
            return false;
        target /= 2;

        vector<int> dp(target + 1, 0);

        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j > 0; j--) {
                if (j >= nums[i]) {
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
                } else {
                    dp[j] = dp[j];
                }
            }
        }

        return dp[target] == target ? 1 : 0;
    }
};