poj1014——Dividing
多重背包问题。转化为01背包问题。不过 需优化，否则会TLE。
优化部分程序中标出。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int f;int a;int cnt;int b,c;int main(){int i,sum,ca=0;int v;while(1){sum=0;for(i=1;i<=6;i++){cin>>a;sum+=a;}if(sum==0) break;printf("Collection #%d:\n",++ca);sum=0;for(i=1;i<=6;i++)sum+=i*a;if(sum%2!=0) {printf("Can't be divided.\n");}else {cnt=0;for(i=1;i<=6;i++)//优化部分{int k=1;while(a-k+1>0){b[++cnt]=i*k;c=i*k;a-=k;k=2*k;}if(a>0){b[++cnt]=i*a;c=i*a;}}v=sum/2;memset(f,-1,sizeof(f));f=0;int j;for(i=1;i<=cnt;i++)for(j=v;j>=0;j--){if(j-b>=0){f=f]+c>f?f]+c:f;}else f=f;} if(f==v) printf("Can be divided.\n"); else printf("Can't be divided.\n");}printf("\n");}return 0;}
页:
[1]