将一堆正整数分为2组，要求2组的和相差最小。
例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。
Input
第1行：一个数N，N为正整数的数量。
第2 - N+1行，N个正整数。
(N <= 100, 所有正整数的和 <= 10000) Output
输出这个最小差 Input示例
5
1
2
3
4
5 Output示例
1
此题可以转换为0-1背包问题，总和为sum, 选定一堆，求出不超过 j 的最大值，那么另一堆的和就可求出，找出其中的最小值即可
物品的重量和价格是一样的
#include <iostream> #include <stdio.h> #include <cstring> #include <math.h> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f int N; int a[110]; int dp[10010]; int sum;int main() {//freopen("1.txt", "r", stdin);cin >> N;for (int i = 1; i <= N; i++) {cin >> a[i];sum += a[i];}memset(dp, 0, sizeof(dp));for (int i = 0; i <= sum; i++)if (a[1] <= i)dp[i] = a[1];elsedp[i] = 0;for (int i = 2; i <= N; i++) {for (int j = sum; j >= 0; j--) { //滚动数组，从右往左if (j >= a[i])dp[j] = max(dp[j], dp[j-a[i]]+a[i]);}}int ret = INF;for (int i = 0; i <= sum; i++) {ret = min(ret, abs(sum-2*dp[i]));}cout << ret;return 0; }
其实最小值是两堆分别从左右逼近sum/2时取得，所以可以求不超过sum/2的最大值，这样就出来的差值就是最小值
#include <iostream> #include <stdio.h> #include <cstring> #include <math.h> #include <algorithm> using namespace std;int N; int a[110]; int dp[10010]; int sum;int main() {//freopen("1.txt", "r", stdin);cin >> N;for (int i = 1; i <= N; i++) {cin >> a[i];sum += a[i];}int h = sum/2;memset(dp, 0, sizeof(dp));for (int i = 0; i <= h; i++)if (a[1] <= i)dp[i] = a[1];elsedp[i] = 0;for (int i = 2; i <= N; i++) {for (int j = h; j >= 0; j--) { //滚动数组，从右往左if (j >= a[i])dp[j] = max(dp[j], dp[j-a[i]]+a[i]);}}int ret;ret = abs(sum - 2*dp[h]);cout << ret;return 0; }