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();
         }
     }
     ;
 }
上一篇:通过RFC给SAP新建用户


下一篇:android手势创建及识别