1 //Accepted    624 KB    16 ms 2 //dp 背包 多重背包 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 120005; 8 int f[imax_n]; 9 int amount[7];10 int v;11 int n=6;12 int max(int a,int b)13 {14     return a>b?a:b;15 }16 void zeroOnePack(int cost,int weight)17 {18     for (int j=v;j>=cost;j--)19     f[j]=max(f[j],f[j-cost]+weight);20 }21 void completePack(int cost,int weight)22 {23     for (int j=cost;j<=v;j++)24     f[j]=max(f[j],f[j-cost]+weight);25 }26 void multiplePack(int cost,int weight,int amount)27 {28     if (cost*amount>=v)29     {30         completePack(cost,weight);31         return ;32     }33     int k=1;34     while (k<amount)35     {36         zeroOnePack(k*cost,k*weight);37         amount-=k;38         k<<=1;39     }40     zeroOnePack(amount*cost,amount*weight);41 }42 void Dp()43 {44     memset(f,0,sizeof(f));45     for (int i=1;i<=n;i++)46     {47         multiplePack(i,i,amount[i]);48     }49     int ans=0;50     for (int i=0;i<=v;i++)51     ans=max(ans,f[i]);52     if (ans==v)53     {54         printf("Can be divided.\n");55     }56     else57     {58         printf("Can‘t be divided.\n");59     }60     printf("\n");61 }62 int main()63 {64     int t=0;65     while (scanf("%d%d%d%d%d%d",&amount[1],&amount[2],&amount[3],&amount[4],&amount[5],&amount[6]),amount[1]+amount[2]+amount[3]+amount[4]+amount[5]+amount[6])66     {67         v=0;68         for (int i=1;i<=n;i++)69         {70             v+=amount[i]*i;71         }72         printf("Collection #%d:\n",++t);73         if (v%2==1)74         {75             printf("Can‘t be divided.\n\n");76         }77         else78         {79             v=v/2;80             Dp();81         }82     }83     return 0;84 }