算法学习之0-1背包问题

题目要求：

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

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum

代码实现：

class Solution {
private:
    // memo[i][c] 标识使用索引为[0...i]的这些元素，是否可以完全填充一个容量为c的背包
    // -1 表示为未计算；0表示不可以填充；1表示可以填充
    vector<vector<int>> memo;

    // 使用nums[0...index], 是否可以完全填充一个容量为sum的背包
    bool tryPartition(const vector<int> &nums, int index, int sum) {
        if (sum == 0)
            return true;
        if (sum < 0 || index < 0)
            return false;

        if (memo[index][sum] != -1)
            return memo[index][sum];

        memo[index][sum] = (tryPartition(nums, index - 1, sum) || tryPartition(nums, index - 1, sum - nums[index])) ? 1 : 0;
        return memo[index][sum] == 1;
    }

public:
    bool canPartition(vector<int> &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            assert(nums[i] > 0);
            sum += nums[i];
        }

        if (sum % 2 != 0)
            return false;

        memo = vector<vector<int>>(nums.size(), vector<int>(sum / 2 + 1, -1));
        return tryPartition(nums, nums.size() - 1, sum / 2);
    }
};

动态规划算法实现：

class Solution {
public:
    bool canPartition(vector<int> &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            assert(nums[i] > 0);
            sum += nums[i];
        }

        if (sum % 2 != 0)
            return false;

        int n = nums.size();
        int C = sum / 2;
        vector<bool> memo(C + 1, false);

        for (int i = 0; i <= C; ++i) {
            memo[i] = (nums[0] == i);
        }

        for (int i = 1; i < n; ++i) {
            for (int j = C; j >= nums[i]; --j) {
                memo[j] = memo[j] || memo[j - nums[i]];
            }
        }

        return memo[C];
    }
};