题意： 将一堆正整数分为2组，要求2组的和相差最小。
例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。
N<=100 sum<=10000
想了个N*sum的lowDP
网上还有背包做法，很神奇
最简单的我觉还是扫一遍，set作为答案暴力更新
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <cstring> #include <set> using namespace std; typedef long long ll; inline void r(ll&num){ num=0;ll f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar(); num*=f; } inline void r(int &num){ num=0;int f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar(); num*=f; } const int maxn = 2e4+10; int dp[110][maxn]; int main() { int n; r(n); int t; dp[0][10000]=1; int val; for(int i=1;i<=n;i++) { r(t); for(int j=0;j+t<=20000;j++) { if(dp[i-1][j]) { val = j-10000; dp[i][val-t+10000] = dp[i-1][j]; dp[i][val+t+10000] = dp[i-1][j]; } } } int x = maxn; for(int i=0;i<=20000;i++) { if(dp[n][i]) { val = i-10000; x = min(x,abs(val)); } } printf("%d ",x); return 0; }