/*日期:2011-10-21
作者:xiaosi
题目: 最少硬币问题
*/
问题描述:
设有n 种不同面值的硬币,各硬币的面值存于数组T〔1:n〕中。现要用这些面值的硬
币来找钱。可以使用的各种面值的硬币个数存于数组Coins〔1:n〕中。
对任意钱数0≤m≤20001,设计一个用最少硬币找钱m的方法。
?编程任务:
对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,
以及钱数m,0≤m≤20001,编程计算找钱m的最少硬币数。
?数据输入:
由文件input.txt 提供输入数据,文件的第一行中只有1 个整数给出n的值,第2 行起每
行2 个数,分别是T[j]和Coins[j]。最后1 行是要找的钱数m。
?结果输出:
程序运行结束时,将计算出的最少硬币数输出到文件output.txt中。问题无解时输出-1。
输入文件示例 输出文件示例
input3
1 3
2 3
5 3
18
output
5
#include<iostream>
using namespace std;
int main()
{
int n,i,m,t,v;
cin>>n;
int *value=new int [n+1],*value1=new int [n+1];
int *q=new int [n+1];
for(i=1;i<=n;i++)
{ cin>>value[i]>>q[i];
value1[i]=value[i]*q[i];}
cin>>m;
int *way=new int [m+1];
int *way1=new int [m+1];
way1[0]=way[0]=0;
for(i=1;i<=m;i++)
{
if(value1[1]>=i&&i%value[1]==0)
way1[i]=way[i]=i/value[1];
else
way1[i]=way[i]=0;
}
int j;
for(j=2;j<=n;j++)
{
for(i=value[j];i<=m;i++)
{
t=1;
while(t<=q[j]&&value[j]*t<=i)
{
if((i-value[j]*t)&&way[i-value[j]*t]==0)
{ t++;
continue;}
else
v=t+way[i-value[j]*t];
if(way1[i]==0||way1[i]>v)
way1[i]=v;
t++;
}
}
for(i=1;i<=m;i++)
{ way[i]=way1[i];
}
}
if(way[m]==0)
way[m]=-1;
cout<<way[m]<<endl;
return 0;
}
分享到:
相关推荐
设计算法求解最少硬币问题,并编程实现,超市找零钱时,找钱数最少的方法
最少硬币问题 动态规划算法 通过ACM网站accept
算法分析 关于动态规划的最少硬币问题的代码,
算法设计-动态规划法解决最少硬币问题源代码
最少硬币问题 动态规划动态规划动态规划动态规划动态规划v
最少零钱问题,最少硬币问题,动态规划算法,找零钱问题,
设有n 种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。...计算出最少硬币数,每个答案一行,问题无解时输出-1。 Sample Input 3 1 3 2 3 5 3 18 Sample Output 5
贪心算法求解最少硬币问题C语言程序,问题描述:给顾客找零钱时,收银处有1元,5角和1角硬币若干,如何用最少数量的硬币找够零钱? 算法思想:比如要找给顾客2元9角钱,首先计算1元最多可以有多少枚,即2枚,减去2元,还...
使用各种面值的硬币,现用这些硬币找钱 对任意钱数,用最少钱币找钱的方法
对于任意钱数,设计一个用最少硬币找钱的方法 数据输入:由文件input.txt提供输入数据,文件的第一行中只有一个整数给出n的值,第二行起每行2个数,分别是T[j]和cion[j].最后一行是要找的钱数m。 解题思路:可以...
最少硬币问题.note
算法的一道题目,最少硬币问题,题目要求是由文件input.txt提供输入数据,文件的第1行中只有1个整数给出 的值,第2行起每行2个数,分别是 和 。最后1行是要找到钱数 。
是学习算法设计与分析所必须的实验代码,经典的1、最少硬币问题;2、最近点对问题;3、世界名画陈列问题;4、最佳调度问题;5、汽车加油问题;6、租用潜艇问题等
用动规实现最少硬币问题 #include #include using namespace std; int n,m; int coins[10],T[10]; int f[20002]; int LeastCoin(int n,int m) { for(int i=0;i;i++) f[i]=i+1; //初始化f数组 f[0]=0; for(int ...
贪心算法——用最少硬币找出n分钱的问题,以及代码。终于解决了
这是一个利用动态规划的最少硬币找零算法,时间效率符合要求
在1次购物中希望使用最少硬币个数。例如,1次购物需要付款0.55元,没有5角的硬币,只好用2*20+10+5共4枚硬币来付款。如果付出1元,找回4角5分,同样需要4枚硬币。但是如果付出1.05元(1枚1元和1枚5分),找回5角,只...