动态规划解决背包问题与分割等和子集

时间复杂度：O(m * n) 空间复杂度：O(m * n)

解题思路：动态规划（一维）

首先读取物品数量 m 和背包容量 n，再分别读取 m 个物品的重量数组 weight 和价值数组 value，接着初始化一个长度为 n + 1 的一维 dp 数组，dp[j] 表示容量为 j 的背包能装下的最大价值，初始值全为 0，然后通过双层循环遍历物品和背包容量，外层循环逐个遍历 m 个物品，内层循环从后往前遍历背包容量从 n 到当前物品重量 weight[i]，这样能避免重复选取同一物品，对于每个容量 j，取不选当前物品保持 dp[j] 原值和选当前物品 dp[j - weight[i]] + value[i]，即容量 j - weight[i] 的最大价值加上当前物品价值中的较大值更新 dp[j]，最终输出 dp[n]，即容量为 n 的背包能获得的最大价值。

具体代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int m;
    int n;
    cin >> m >> n;
    vector<int> weight(m, 0);
    vector<int> value(m, 0);
    for (int i = 0; i < m; i++) cin >> weight[i];
    for (int i = 0; i < m; i++) cin >> value[i];
    vector<int> dp(n + 1, 0);
    for (int i = 0; i < m; i++) {
        for (int j = n; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[n];
    return 0;
}

时间复杂度：O(m * n) 空间复杂度：O(n)

分割等和子集（LeetCode 416）

解题思路：动态规划（二维）

首先计算数组所有元素的总和，若总和为奇数则直接返回 false，无法分割为两个和相等的子集，若为偶数则将目标值 target 设为总和的一半，即需找到子集和为 target，接着初始化一个二维 dp 数组 dp[i][j] 表示前 i + 1 个元素中选取若干个，能组成的不超过 j 的最大和，并初始化第一行，当 j 大于等于第一个元素值时，dp[0][j] 赋值为该元素值，然后通过双层循环遍历剩余元素和所有可能的和，若当前 j 小于第 i 个元素值，则无法选取该元素，dp[i][j] 等于上一行同列值，否则取不选该元素 dp[i - 1][j] 和选该元素 dp[i - 1][j - nums[i]] + nums[i] 的较大值更新 dp[i][j]，过程中若发现 dp[i][j] 等于 target 则提前返回 true，若遍历结束未找到则返回 false。

具体代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) sum += nums[i];
        if(sum % 2) return false;
        int target = sum / 2;
        vector<vector<int>> dp(nums.size(), vector<int>(target + 1, 0));
        for (int j = 0; j <= target; j++)
            if (j >= nums[0]) dp[0][j] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 1; j <= target; j++) {
                if (j < nums[i]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                if (dp[i][j] == target) return true;
            }
        }
        return false;
    }
};

时间复杂度：O(n * target) 空间复杂度：O(n * target)

解题思路：动态规划（一维）

首先计算数组所有元素的总和，若总和为奇数则直接返回 false，无法分割为两个和相等的子集，若为偶数则将目标值 target 设为总和的一半，即需找到子集和为 target，接着初始化长度为 target + 1 的一维 dp 数组 dp[j] 表示选取若干元素能组成的不超过 j 的最大和，初始值全为 0，然后通过双层循环遍历数组元素和目标和，外层逐个遍历数组元素，内层从后往前遍历 target 到当前元素值避免重复选取同一元素，对每个 j 取不选当前元素保持 dp[j] 原值和选当前元素 dp[j - nums[i]] + nums[i] 的较大值更新 dp[j]，过程中若发现 dp[target] 等于 target 则提前返回 true，若遍历结束未满足条件则返回 false。

具体代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (sum % 2) return false;
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        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]);
                if (dp[target] == target) return true;
            }
        }
        return false;
    }
};

时间复杂度：O(n * target) 空间复杂度：O(target)