最少硬幣問題

設(shè)有n 種不同面值的硬幣，各硬幣的面值存于數(shù)組T［1:n］中?，F(xiàn)要用這些面值的硬幣來找錢?？梢允褂玫母鞣N面值的硬幣個(gè)數(shù)存于數(shù)組Coins［1:n］中。
對(duì)任意錢數(shù)0≤m≤20001，設(shè)計(jì)一個(gè)用最少硬幣找錢m的方法。

編程任務(wù)：
對(duì)于給定的1≤n≤10，硬幣面值數(shù)組T和可以使用的各種面值的硬幣個(gè)數(shù)數(shù)組Coins，以及錢數(shù)m，0≤m≤20001，編程計(jì)算找錢m的最少硬幣數(shù)。

Input

輸入包括多組測(cè)試數(shù)據(jù)，每組輸入的第一行中只有1 個(gè)整數(shù)給出n的值,第2 行起每
行2 個(gè)數(shù)，分別是T[j]和Coins[j]。每組輸入最后1 行是要找的錢數(shù)m。

Output

Sample Input

3
1 3
2 3
5 3
18

Sample Output

5

         動(dòng)態(tài)規(guī)劃題。

代碼如下：

#include<cstdio>
int main()
{
    int t[11],coins[11],c[11][20002];//c[i][j]前i種硬幣找j塊錢最少硬幣數(shù)
    int i,j,n,m,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d %d",&t[i],&coins[i]);
        }
        scanf("%d",&m);
        for(i=1;i<=n;i++)        //初始化
            for(j=0;j<=m;j++)
            {
                if(j==0)
                    c[i][j]=0;
                else if(i==1)  
                    if(j%t[i]==0&&j/t[i]<=coins[i])
                        c[1][j]=j/t[i];
                    else
                        c[1][j]=1000000;
                else
                    c[i][j]=1000000;
            }

        for(i=2;i<=n;i++)        //構(gòu)造c數(shù)組
            for(j=1;j<=m;j++)
                for(k=0;k<=coins[i];k++)
                {
                    if(c[i][j]>(c[i-1][j-k*t[i]]+k)&&(j-k*t[i])>=0)
                            c[i][j]=c[i-1][j-k*t[i]]+k;
                }
        if(c[n][m]!=1000000)
        {
            printf("%d\n",c[n][m]);
        }
        else
            printf("-1\n");
    }
    return 0;
}

題目地址：http://acm.nankai.edu.cn/p1132.html