最少硬幣問題
設有n 種不同面值的硬幣，各硬幣的面值存于數組T［1:n］中。現要用這些面值的硬幣來找錢。可以使用的各種面值的硬幣個數存于數組Coins［1:n］中。
對任意錢數0≤m≤20001，設計一個用最少硬幣找錢m的方法。
編程任務：
對于給定的1≤n≤10，硬幣面值數組T和可以使用的各種面值的硬幣個數數組Coins，以及錢數m，0≤m≤20001，編程計算找錢m的最少硬幣數。
Input
輸入包括多組測試數據，每組輸入的第一行中只有1 個整數給出n的值,第2 行起每
行2 個數，分別是T[j]和Coins[j]。每組輸入最后1 行是要找的錢數m。
Output
對于每組輸入數據，輸出一行，即計算出最少硬幣數。問題無解時輸出-1。
Sample Input
3
1 3
2 3
5 3
18
Sample Output
5
動態規劃題。
代碼如下：
#include<cstdio>
int main()
{
int t[11],coins[11],c[11][20002];//c[i][j]前i種硬幣找j塊錢最少硬幣數
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++) //構造c數組
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
posted on 2010-09-17 13:32
jince 閱讀(3797)
評論(0) 編輯 收藏 引用 所屬分類:
Questions