首页 > 代码库 > POJ 1014 Dividing
POJ 1014 Dividing
多重背包的可行性问题。
题意是说有 1~6 种石头,分别价值1~6 。然后有不同的数量,问你能不能平均分给两个人。
这时候可以把价值当作费用,求能不能到达 总价值的一半。即讲背包的容量设为 总价值的一半,能否装满。
据说有个很强大的“剪树” 1~6的最小公倍数是60 。
个数超过60……if(n&1)n=61; else n=60;
ORZ……没想到,也没用这个。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; int n,m; int dp[7][150001]; int Cot[7]; int Cost[7]; int main() { int cc=1; while(1) { bool flag=1; m=0; for(int i=1; i<7; i++) { int tmp; scanf("%d",&tmp); if(tmp)flag=0; Cost[i]=i,Cot[i]=tmp; m+=Cost[i]*Cot[i]; } if(flag)return 0; memset(dp,-1,sizeof(dp)); printf("Collection #%d:\n",cc++); if(m&1) { puts("Can't be divided.\n"); continue; } else m/=2; dp[0][0]=0; for(int i=1; i<7; i++) { for(int j=0; j<=m; j++) { if(dp[i-1][j]>=0) dp[i][j]=Cot[i]; else dp[i][j]=-1; } for(int j=0; j<=m-Cost[i]; j++) { if(dp[i][j]>0) dp[i][j+Cost[i]]=max(dp[i][j+Cost[i]],dp[i][j]-1); } } if(dp[6][m]==-1) puts("Can't be divided.\n"); else puts("Can be divided.\n"); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。