POJ Charlie's Change 查理之转换（多重背包，变形）

题意:

　　给定身上的4种硬币，分别是1 ，5 ，10， 25面额各有多张，要求组成面额p的硬币尽可能多。输出组成p的4种硬币各自的数量。

思路：

　　多重背包，300+ms。用01背包+二进制的方法。记录下所有的硬币的个数以及4种硬币分别的个数，注意初始化dp数组的不同之处。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define LL long long

 using namespace std;

 const int  N=, INF=-;

 int coin[]={, , , };

 int dp[N][], num[];

 int p;

 void cal()

 {

     memset(dp,,sizeof(dp));

     for(int i=; i<=p; i++) dp[i][]=INF;

     for(int i=; i<; i++)

     {

         int k=, tmp=num[i];

         while()

         {

             if(k>tmp&&tmp)    k=tmp;

             else if(k>tmp)    break;

             for(int j=p; j>=k*coin[i]; j--)

             {

                 if( dp[j-k*coin[i]][]!=INF &&dp[j][]<dp[j-k*coin[i]][]+k)

                 {

                     dp[j][]=dp[j-k*coin[i]][]+k;

                     for(int c=; c<=i+; c++)       //复制次数

                         dp[j][c]=dp[j-k*coin[i]][c];

                     dp[j][i+]+=k;  //添加次数

                 }

             }

             tmp-=k;

             k<<=;

         }

     }

     if(dp[p][]==INF)    printf("Charlie cannot buy coffee.\n");

     else    printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", dp[p][], dp[p][], dp[p][], dp[p][] );

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     while(cin>>p,p)

     {

         int cnt=;

         for(int i=; i<; i++)

         {

             scanf("%d", &num[i]);

             cnt+=num[i]*coin[i];

         }

         if(cnt<p)

         {

             printf("Charlie cannot buy coffee.\n");

             continue;

         }

         cal();

     }

     return ;

 }

AC代码