用C语言实现题目 昊城国庆假期发明了一款小游戏： 给定1，2，.....，n-1, n的n个正整数，要把这n个数，分割为2部分，其中一部分包含在A集合中，另外的包含在B集合中。 假设A集合中所有数的累加和为SA, B集合中所有数的累加和为SB， 目标是找到这样一种分割，使得SA和SB的差值最小，即|SA-SB|达到最小值。 请输出这个最小值

以下是用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);

    int* nums = (int*)malloc(sizeof(int) * n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
        sum += nums[i];
    }

    int target = sum / 2;
    int* dp = (int*)malloc(sizeof(int) * (target + 1));
    for (int i = 0; i <= target; i++) {
        dp[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = min(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }

    int ans = abs(sum - dp[target] - dp[target]);
    printf("%d\n", ans);

    free(nums);
    free(dp);

    return 0;
}

算法思路：

将原问题转化为背包问题，把所有数的和除以2得到target，然后就是一个01背包问题，要求选出一些数，使它们的和最接近target。具体地，用dp[i]表示选出若干个数，它们的和最接近i，那么最终的答案就是abs(sum - dp[target] - dp[target])。

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

空间复杂度：O(target)