poj 1787（記録パス＋多重リュックサック）

住所:http://poj.org/problem?id=1787
Charie's Change
Time Limit: 1000 MS
 
メモリLimit: 30000 K
Total Submissions: 2689
 
Acceepted: 721
Description
Charie is a driver of Advanced Cargo Movement，Ltd.Charie drives a lot and so he offten buys coffee at coffee ventding machinerst.Charie hates change.That is baicallythe sep of your next. 
Your program will be given numbers and types of coins Chare has and the coffee price.The coffee ventding Machines accept coins of values 1，5，10，and 25 cents.The program shout put which coins Charie has to use paying the coffee so that he uses as many coins as possible.Because Charie really does not want change back want hents pants the prext. 
Input
Each line of the input contains five integer numbers separated by a single spspace describing situation to solive.The first integer on the line P，1<=10,000，isthe coffee price in cents.Next fourintetets.Next fourininintetetededededededededededests.ininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininents.Nets.Nexs.Nexs），and quararters(25 cents)in Chare's valet.The last line of the input contains five zros andのout put shoul d be generated for it.
Output
For each situation，your program shoutput one line containing the sting“Throw in T 1 cents，T 2 nikels，T 3 dimes，and T 4 quares.”，where T 1，T 3，T 3T 4 are the numbers of coins of apprate values Chare share to pay the coffee while using as many coins as possible.In the case Chare does not possess enough change to pay the pay the coffice of the coffice profile profirel。
Sample Input

12 5 3 1 2
16 0 0 0 1
0 0 0 0 0

Sample Output

Throw in 2 cents, 2 nickels, 0 dimes, and 0 quarters.
Charlie cannot buy coffee.

面の値は1、5、10、25の4種類の硬貨で、それぞれc 1、c 2、c 3、c 4枚があります。
考え方：多重：4種類の硬貨しかないので、非常に暴力的な記録方法を使っています。
           完全：シミュレーションで出てきたのです。詳細はコードを参照してください。
コード:
多重リュックサック:

#include
#include
#include
using namespace std;
int dp[10010][5];  //          
int main()
{
    int v,c[5],i;
    int cent[5]= {0,1,5,10,25};
    while(scanf("%d%d%d%d%d",&v,&c[1],&c[2],&c[3],&c[4])>0)
    {
        if(!v&&!c[1]&&!c[2]&&!c[3]&&!c[4]) break;
        memset(dp,0,sizeof(dp));
        for(int s=1; s<5; s++)
        {
            if(c[s]*cent[s]>=v)
            {
                for(i=cent[s]; i<=v; i++)
                {
                    if(!(i==cent[s]||dp[i-cent[s]][0])) continue;
                    int k=max(dp[i][0],dp[i-cent[s]][0]+1);
                    if(k>dp[i][0])
                    {
                        dp[i][0]=k;
                        for(int j=1;j<=s;j++)
                        {
                            if(j==s) dp[i][j]=dp[i-cent[s]][j]+1;
                            else dp[i][j]=dp[i-cent[s]][j];
                        }
                    }
                }
            }
            else
            {
                int m=1;
                while(c[s])
                {
                    c[s]-=m;
                    for(i=v; i>=m*cent[s]; i--)
                        if(i==m*cent[s]||dp[i-m*cent[s]][0])
                        {
                            int k=max(dp[i-m*cent[s]][0]+m,dp[i][0]);
                            if(k>dp[i][0])
                            {
                                dp[i][0]=k;
                                for(int j=1;j<=s;j++)
                                {
                                    if(j==s) dp[i][j]=dp[i-m*cent[s]][j]+m;
                                    else dp[i][j]=dp[i-m*cent[s]][j];
                                }
                            }
                        }
                    m=m<<1;
                    if(m>c[s]) m=c[s];
                }
            }
        }
        if(dp[v][0]) printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.
",dp[v][1],dp[v][2],dp[v][3],dp[v][4]);
        else printf("Charlie cannot buy coffee.
");
    }
    return 0;
}  //          ，  dp[i][0]      ，         ，       。（ 01        ，             ）

完全リュックサック:

#include
#include
#include
using namespace std;
int dp[10010][2],used[10010];
int main()
{
    int v,c[50],i,j;
    int cent[5]= {0,1,5,10,25};
    while(scanf("%d",&v)>0,v)
    {
        memset(dp,0,sizeof(dp));
        for(i=1; i<=4; i++) scanf("%d",&c[i]);
        for(i=1; i<=4; i++)
        {
            memset(used,0,sizeof(used));
            for(j=cent[i]; j<=v; j++)
            {
                if(dp[j-cent[i]][0]+1>dp[j][0]&&(dp[j-cent[i]][0]||j==cent[i])&&used[j-cent[i]]+1<=c[i])
                {
                    dp[j][0]=dp[j-cent[i]][0]+1;  //             
                    dp[j][1]=j-cent[i];  //    
                    used[j]=used[j-cent[i]]+1;  //         
                }
            }
        }
        if(!dp[v][0]) printf("Charlie cannot buy coffee.
");
        else
        {
            c[1]=c[5]=c[10]=c[25]=0;
            i=v;
            while(i)
            {
                c[i-dp[i][1]]++;  //         
                i=dp[i][1];
            }
            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.
",c[1],c[5],c[10],c[25]);
        }
    }
    return 0;
}