hdu 1059 Dividing(优化的多重背包 可达可不达)

发布时间:2014-10-22 19:59:19
来源:分享查询网

http://acm.hdu.edu.cn/showproblem.php?pid=1059 题意:有六种marbles,第i种marbles的价值为i,数量为输入的num[i],两个人想按这些marbles的总价值平分,问他们是否能够平分成功. 思路:和hdu 1171 http://acm.hdu.edu.cn/showproblem.php?pid=1171 类似。能不能平分,可以按总价值的一半进行多重背包,若总价值一半能够到达,说明平分成功,不过这里需要进行优化。直接转化为01背包,TLE。。 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int dp[60010],use[60010],sum; int num[10]; //优化的多重背包 void solve() { sum = sum>>1; memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i = 1; i <= 6; i++) { if(num[i] > 0) { memset(use,0,sizeof(use)); for(int j = i; j <= sum; j++) { if(dp[j-i] && !dp[j] && use[j-i] < num[i]) { dp[j] = 1; use[j] = use[j-i]+1; } } } } if(dp[sum]) printf("Can be divided.\n\n"); else printf("Can't be divided.\n\n"); } int main() { int item = 1; while(~scanf("%d %d %d %d %d %d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6])) { if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0&&num[5]==0&&num[6]==0) break; sum = 0; for(int i = 1; i <= 6; i++) sum += num[i]*i; if(sum%2 != 0) { printf("Collection #%d:\nCan't be divided.\n\n",item++); continue; } else { printf("Collection #%d:\n",item++); solve(); } } return 0; }

返回顶部
查看电脑版