2011-06-10 19:43:48Morris

d904. 換零錢

http://zerojudge.tw/ShowProblem?problemid=d904

內容 :

可憐的貝茜在Slobbovia邊境的便利商店工作。Slobbovian國的人使用不同與美國不同的幣值,而且幣值隨時在更動!

請你幫助貝茜做出最佳情況硬幣數給Slobbovian顧客。你需要用N(1<=N<=10)種不同的硬幣數提供C(1<=C<=1000)美分給顧客。你可以假設所有的測資都是可以用此N種硬幣提供出來的。

舉例:如果有5種不同的幣值50,25,10,5,1可用,貝茜將找出93美分的最佳情況硬幣數(最少的硬幣),用1個50,1個25,1個10,1個5,3個1的硬幣(共7個硬幣)為最佳硬幣數。

那能有多難呢?最後兩個測資較具有挑戰性。

輸入說明 :

每筆測資的第1行有兩數字C與N,其中用一個空格隔開 接下來的第2到第N+1行為各種不同的幣值

輸出說明 :

輸出最佳情況硬幣數

範例輸入 :

93 5
25
50
10
1
5

範例輸出 :

7

提示 :

出處 :

USACO 2007 January Competition (管理:B88000005)

作法 : DP

/**********************************************************************************/
/*  Problem: d904 "換零錢" from USACO 2007 January Competition                 */
/*  Language: C                                                                   */
/*  Result: AC (2ms, 254KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-06-04 21:59:35                                     */
/**********************************************************************************/


#include<stdio.h>
main() {
    int a, b, c, n;
    while(scanf("%d %d", &c, &n) == 2) {
        int DP[1001] = {}, money[10];
        for(a = 0; a < n; a++)    scanf("%d", &money[a]);
        for(a = 0; a <= c; a++)
            for(b = 0; b < n; b++)
                if(a + money[b] <= c) {
                    if(DP[a + money[b]] == 0) {
                        if(a == 0)
                            DP[a + money[b]] = 1;
                        else
                            DP[a + money[b]] = DP[a] + 1;
                    }
                    else if(DP[a + money[b]] > DP[a] + 1)
                        DP[a + money[b]] = DP[a] + 1;
                }
        printf("%d\n", DP[c]);
    }
    return 0;
}