最少硬币问题
设有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()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int t[11],coins[11],c[11][20002];//c[i][j]前i种硬币找j块钱最少硬币数
int i,j,n,m,k;
while(scanf("%d",&n)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d %d",&t[i],&coins[i]);
}
scanf("%d",&m);
for(i=1;i<=n;i++) //初始化
for(j=0;j<=m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=2;i<=n;i++) //构造c数组
for(j=1;j<=m;j++)
for(k=0;k<=coins[i];k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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 阅读(3729)
评论(0) 编辑 收藏 引用 所属分类:
Questions