POJ 1787 Charlie's Change 最多金币

原題： http://poj.org/problem?id=1787

題目：

Charlie’s Change

Time Limit: 1000MS Memory Limit: 30000K

Total Submissions: 3520 Accepted: 1043

Description

Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at coffee vending machines at motorests. Charlie hates change. That is basically the setup of your next task.

Your program will be given numbers and types of coins Charlie has and the coffee price. The coffee vending machines accept coins of values 1, 5, 10, and 25 cents. The program should output which coins Charlie has to use paying the coffee so that he uses as many coins as possible. Because Charlie really does not want any change back he wants to pay the price exactly.

Input

Each line of the input contains five integer numbers separated by a single space describing one situation to solve. The first integer on the line P, 1 <= P <= 10 000, is the coffee price in cents. Next four integers, C1, C2, C3, C4, 0 <= Ci <= 10 000, are the numbers of cents, nickels (5 cents), dimes (10 cents), and quarters (25 cents) in Charlie’s valet. The last line of the input contains five zeros and no output should be generated for it.

Output

For each situation, your program should output one line containing the string “Throw in T1 cents, T2 nickels, T3 dimes, and T4 quarters.”, where T1, T2, T3, T4 are the numbers of coins of appropriate values Charlie should use to pay the coffee while using as many coins as possible. In the case Charlie does not possess enough change to pay the price of the coffee exactly, your program should output “Charlie cannot buy coffee.”.

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.

思路：

輸入需要湊齊的面值P，輸入四種貨币的數目，面值分别為1,5,10,25，求出一種可以湊齊P的方案，要求使用的金币數最多。

顯然，這種有數量限制的貨币我們可以看作是多重背包，就按多重背包的處理方式求最大貨币數。至于難點如何求出最大具體的方案，我們隻需要用一個path[]數組儲存過程就可以了。

上式代表這當容量為j的時候，path[j]儲存的是用了此物品剩下的金額。

反過來推，就有value[i]=path[j]-j。

while(path[i]!=-1)      
{
      ans[i-path[i]]++;
      i=path[i];
}

           

這裡就是利用上面的反推結果，每次能得到目前狀态最後一次放入的物品的金額。

i表示目前剩餘價值，直到最後一個都沒放的時候，就有i=0，path[i]!=1就是搜尋結果。

然後就可以輸出方案了。

代碼：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

const int INF = ;
const int N = ;
int value[]={,,,,};
int num[];     //記錄每種貨币的數目
int dp[N];      //記錄目前容量的最大數目
int ans[];    //ans[25]表示面值為25的數目
int used[N];    //記錄該次操作的該物品使用了幾次
int path[N];    //用于反推結果
int n;          //要求的金額


void init()
{
    memset(num,,sizeof(num));
    memset(path,,sizeof(path));
    memset(num,,sizeof(num));
    memset(ans,,sizeof(ans));
    for(int i=;i<=n+;i++)
    {
        dp[i]=-INF;                 //将所有金額下需要的貨币初始化無窮小，如果不存在滿足的方案，那dp[總金額]=無窮小；
    }
    path[]=-;                     //用于反推的時候找到終點，path[0]即為不需要在增加貨币數了。
    dp[]=;
}

void pack()
{
    for(int i=;i<=;i++)
    {
        memset(used,,sizeof(used));//used數組是對目前物品的使用次數進行計數，是以每次變更貨币就需要清零一次
        for(int j=value[i];j<=n;j++)
        {
            //顯然，一維dp第二重循環表示的是完全背包
            //j-value[i]表示的是用第i個貨币去先裝入背包的剩下金額
            //used[j-value[i]]<num[i]表示如果本次不放，已放的件數必須要比總數小，
        //used[j-value[i]]<=num[i]-1，這樣才能有物品放進去
            //dp[j-value[i]]>=0表示前一次的狀态可以實作，如果不滿足即代表dp[j-value[i]]=-INF，
        //視為前面的貨币湊不夠此狀态，後面的計算就不能用這個結果。
            //dp[j]<dp[j-value[i]]+1表示放了此物品的數目一定要比不放的情況下數目要多，否則不是最優解


            if(dp[j]<dp[j-value[i]]+&&dp[j-value[i]]>=&&used[j-value[i]]<num[i])
            {
                dp[j]=dp[j-value[i]]+;     //放了此物品，等于此物品的個數1加上剩下容量能放的最大個數。
                used[j]=used[j-value[i]]+; //放了此物品的個數等于不放此物品的時候放的個數加1
                path[j]=j-value[i];         //用于記錄求最優解具體狀态，即目前容量放了此物品之後剩下的容量
            }
        }
    }
}

void findans()
{
    if(dp[n]<)
    {
          printf("Charlie cannot buy coffee.\n");
          return;
    }
    else
    {
        int i=n;
        while(path[i]!=-)      
        {
            ans[i-path[i]]++;
            i=path[i];
        }
        printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",
        ans[value[]],ans[value[]],ans[value[]],ans[value[]]);
    }
}


int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int sum=n;
        init();                         //對于操作的每次測試都需要初始化
        for(int i=;i<=;i++)
        {
            scanf("%d",&num[i]);
            sum=sum+num[i];
        }
        if(sum==)  break;              //因為各項都為大于等于0的數，其和為0即所有數都為0
        pack();
        findans();
    }
    return ;
}