c++题解 | #分割等和子集#

思路转移：从一个数组中取数字，每个数字只能取一次，问取出的数字之和与未取出的数字之和能否相等。
分析：一个数组中的所有数字分为两部分，问两部分的和能否相等，很明显，如果整个数组的和(s)是奇数，必然不能。当为偶数，则判断是否能在数组中取出一些数，使得它们的和为s/2。
这样问题转移为：容量为s/2的背包，nums保存多个物品的重量，每个物品仅有一个，问能否把背包装满？
dp[i]表示 当容量为i时，背包能最多装多重的物品。答案就是dp[s/2]==s/2，当容量为s/2时，看最大能装重量是否是s/2?
转移：dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])，当j>=nums[i]时。
先遍历物品，再遍历容量：

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 501;
const int M = 500*100+10;
int nums[N];
int dp[M];
// 就像 在容量为s/2的背包中放一些重量为nums[i]的物品，问能否恰好放满整个背包（这里放满也就是最大重量）
int main() {
    int n;
    scanf("%d", &n);
    int s = 0;
    for(int i = 0; i < n;i ++){
        scanf("%d", &nums[i]);
        s += nums[i];
    }
    if(s%2)
        printf("false");
    else{
        int t = s/2;
        //遍历物品
        for (int i=0; i<n; i++) {
            //遍历重量
            for(int j = t; j>=0;j--){
                if(j-nums[i]>=0){
                    dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
                }
            }
        }
        if(dp[t]==t) //如果最大能放的重量==目标（放满）
            printf("true");
        else{
            printf("false");
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")