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

发布时间:2014-10-22 19:59:19编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 1059 Dividing(优化的多重背包 可达可不达)",主要涉及到hdu 1059 Dividing(优化的多重背包 可达可不达)方面的内容,对于hdu 1059 Dividing(优化的多重背包 可达可不达)感兴趣的同学可以参考一下。

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; }


上一篇:尝鲜C#
下一篇:OCP-1Z0-053-V13.02-702题

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款