刷题记录：lc416分割等和子集

日期：2025-05-07

题目大意

给出一个数组，判断是否能分成两个子集，和相同

解题思路

• 暴力：指数级别超时，因此使用dp优化，可抽象为01背包问题，数值为物品，和为背包 重量=价值=物品数值本身。 因此可判断是否装满：dp[target]==target
• 状态转移方程：dp[j]=(dp[j],dp[j-weight[i]+value[i])
• 初始化：dp[0]=0 防止滚动数组被初始值覆盖
• 遍历顺序：for（）物品 for（倒序）背包 01背包只能使用一次物品，不可颠倒，且倒序

AC 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n) {
        vector<int> nums(n);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
            sum += nums[i];
        }

        if (sum % 2 != 0) {//如果总和是奇数，直接不可能平分
            cout << "false" << endl;
            continue;
        }

        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= nums[i]; j--) { 
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);//dp[j]表示容量为j的背包最多能装多大价值的物品
            }
        }

        if (dp[target] == target) {//判断是否装满
            cout << "true" << endl;
        } else {
            cout << "false" << endl;
        }
    }
    return 0;
}

今日总结

• 动态规划五部曲：
• 1.dp数组和下标的含义
• 2.确定递推公式
• 3.dp数组细究如何初始化
• 4.确定遍历顺序
• 5.打印举例推导dp数组
• 01背包的遍历顺序不能颠倒，是先物品再背包，保证只拿一次。二维可以
• 一维：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
• 二维：dp[i-1]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

← 返回我的学习主页