poj1014——Dividing

44424742

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