poj1014 dp 多重背包

 //Accepted    624 KB    16 ms //dp 背包 多重背包 #include <cstdio> #include <cstring> #include <iostream> using namespace std; ; int f[imax_n]; ]; int v; ; int max(int a,int b) {     return a>b?a:b; } void zeroOnePack(int cost,int weight) {     for (int j=v;j>=cost;j--)     f[j]=max(f[j],f[j-cost]+weight); } void completePack(int cost,int weight) {     for (int j=cost;j<=v;j++)     f[j]=max(f[j],f[j-cost]+weight); } void multiplePack(int cost,int weight,int amount) {     if (cost*amount>=v)     {         completePack(cost,weight);         return ;     }     ;     while (k<amount)     {         zeroOnePack(k*cost,k*weight);         amount-=k;         k<<=;     }     zeroOnePack(amount*cost,amount*weight); } void Dp() {     memset(f,,sizeof(f));     ;i<=n;i++)     {         multiplePack(i,i,amount[i]);     }     ;     ;i<=v;i++)     ans=max(ans,f[i]);     if (ans==v)     {         printf("Can be divided.\n");     }     else     {         printf("Can't be divided.\n");     }     printf("\n"); } int main() {     ;     ],&amount[],&amount[],&amount[],&amount[],&amount[]),amount[]+amount[]+amount[]+amount[]+amount[]+amount[])     {         v=;         ;i<=n;i++)         {             v+=amount[i]*i;         }         printf("Collection #%d:\n",++t);         ==)         {             printf("Can't be divided.\n\n");         }         else         {             v=v/;             Dp();         }     }     ; }