將一堆正整數(shù)分為2組，要求2組的和相差最小。

顯然我們可以把所有可能組合成的數(shù)求出來。

然后從總和的中間開始往大找，找到了就是其中一個的分組，就可以求出答案了。

#include<cstdio> #include<algorithm> #define REP(i, a, b) for(int i = (a); i < (b); i++) using namespace std;const int MAXN = 11234; int f[MAXN], w[MAXN], n, sum;int main() {f[0] = 1;scanf("%d", &n);REP(i, 0, n){scanf("%d", &w[i]);sum += w[i];}REP(i, 0, n)for(int j = sum; j >= w[i]; j--)if(f[j - w[i]])f[j] = 1;for(int ans = (sum + 1) / 2; ans <= sum; ans++)if(f[ans]){printf("%d\n", ans - (sum - ans));break;}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/sugewud/p/9819440.html

總結(jié)

以上是生活随笔為你收集整理的51nod 正整数分组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。