51NOD1007——整数分组（01背包）

将一堆正整数分为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

其实就是把背包容量视为总和除以2的01背包。

因为要让差值小，就是使得一组的和接近s/2.

#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> using namespace std; const int MAXN =10000+10; const long long INF =1000000007 ; const long long MOD =(1ll<<32); const double EPS=1e-8; const double pi = acos(-1); int a[MAXN]; int dp[MAXN]; int main() { int n; scanf("%d",&n); int s=0; for(int i=0;i<n;i++){ scanf("%d",a+i); s+=a[i]; } int m=s/2; for(int i=0;i<n;i++){ for(int v=m;v>=a[i];v--){ dp[v]=max(dp[v],dp[v-a[i]]+a[i]); } } int res=0; printf("%d\n",s-2*dp[m]); }