首页 > 代码库 > UVa 10032 - Tug of War
UVa 10032 - Tug of War
题目:有n个人分成两组,两组人数差不能超过1,找到两组的人重量之差的最小值。
分析:dp,状态压缩01背包。zoj1880升级版。
首先,考虑二维背包。
因为必须放在两个组中的一组,直接背包所有可到状态,取出相差不超过 1的最接近 sum/2的值即可。
然后,优化。
如果直接利用二维背包,由于数据组数较多会TLE,这里利用状态压缩的一维背包;
状态:f(i)表示总重为i时的所有可能的人数,f(i)的值,的第k位上的数是1则代表有k人的组合方式。
转移:f(i)= f(i)| (f(i-w[j])<< 1),等于可以更新到本状态的状态人数集合各加1与原来集合的合。
最后,扫描。
从sum/2开始向下扫描,找到第一个满足题意的解即可。
说明:注意输入0个人的情况。
#include <stdio.h> #include <stdlib.h> #include <string.h> long long f[23001]; int h[101]; int gcd(int a, int b) { return a%b?gcd(b, a%b):b; } int main() { int t,n,sum,r; while (scanf("%d",&t) != EOF) while (t --) { scanf("%d",&n); sum = 0; for (int i = 1 ; i <= n ; ++ i) { scanf("%d",&h[i]); sum += h[i]; } //荣量优化 r = 1; if (n > 0) { r = h[1]; for (int i = 2 ; i <= n ; ++ i) r = gcd(r, h[i]); sum /= r; for (int i = 1 ; i <= n ; ++ i) h[i] /= r; } for (int i = sum/2 ; i >= 0 ; -- i) f[i] = 0LL; f[0] = 1LL; for (int i = 1 ; i <= n ; ++ i) for (int j = sum/2 ; j >= h[i] ; -- j) f[j] |= f[j-h[i]]<<1; int move = sum/2+1; while (move --) { if (n%2 == 0 && f[move]&(1LL<<((n+1)/2))) break; if (n%2 == 1 && f[move]&(1LL<<((n+0)/2))) break; if (n%2 == 1 && f[move]&(1LL<<((n+1)/2))) break; } printf("%d %d\n",move*r,(sum-move)*r); if (t) printf("\n"); } return 0; }
UVa 10032 - Tug of War
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。