51nod-正整数分组问题(基础方程DP-01背包)

正整数分组

将一堆正整数分为2组，要求2组的和相差最小。 例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。

---

思路：

这题的实质其实也是0-1背包问题，但是要想理解到这一步，或者说想要用0-1背包来解决这个问题，就必须将问题抽象化到一定的程度才可以。

一列数，无序，给他分成两半，要想实现两半的和的差最小，就是恨不得恰好均分了。那么我们按照0-1背包的那种”一维式“的思维来想，这个问题就别转化成了从第一个数开始到最后一个数，选出一些数，使他们的和最大程度的接近所有数的和的一半，将这些数作为一组，那么剩下的数就是另一组了。

按照之前0-1背包的思路，这题就迎刃而解了。

---

#include <cmath> #define INF 65535 using namespace std;int n; int f[10007]; int sum; int num[107];int main() {int other;while(~scanf("%d",&n)){sum = 0;for(int i = 1;i <= n;i++){scanf("%d",&num[i]);sum += num[i];}memset(f,0,sizeof(f));for(int i = 1;i <= n;i++)for(int j = sum/2;j >= num[i];j--)f[j] = max(f[j],f[j-num[i]]+num[i]);other = sum - f[sum/2];printf("%d\n",abs(other-f[sum/2]));}return 0; }

 

转载于:https://www.cnblogs.com/immortal-worm/p/4932863.html

总结

以上是生活随笔为你收集整理的51nod-正整数分组问题(基础方程DP-01背包)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。