最少硬币问题最少硬币问题
3-4 最少硬币问题
,问题描述:
设有n种不同面值的硬币,各硬币的面值存于数组T,1:n,中。现要用这些面值的硬
币来找钱。可以使用的各种面值的硬币个数存于数组Coins,1:n,中。
对任意钱数0?m?20001,设计一个用最少硬币找钱m的方法。 ,编程任务:
对于给定的1?n?10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,
以及钱数m,0?m?20001,编程计算找钱m的最少硬币数。 ,数据输入:
由文件coins*.in提供输入数据,文件的第一行中只有1个整数给出的值,第2...
最少硬币问题
3-4 最少硬币问题
,问题描述:
设有n种不同面值的硬币,各硬币的面值存于数组T,1:n,中。现要用这些面值的硬
币来找钱。可以使用的各种面值的硬币个数存于数组Coins,1:n,中。
对任意钱数0?m?20001,
一个用最少硬币找钱m的方法。 ,编程任务:
对于给定的1?n?10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,
以及钱数m,0?m?20001,编程计算找钱m的最少硬币数。 ,数据输入:
由文件coins*.in提供输入数据,文件的第一行中只有1个整数给出的值,第2行起每行n2个数,分别是T[j]和Coins[j]。最后1行是要找的钱数m。 ,结果输出:
程序运行结束时,将计算得出的最少硬币数输出到文件coins*.out中。问题无解时输出-1。
输入文件示例 输出文件示例
coins0.in coins0.out
3 5
1 3
2 3
5 3
18
#include
void Swap(long& a,long& b); void main()
{ long i=0,kind=0,k=0,j=0;
ifstream inf("input.txt");
ofstream outf("output.txt");
//读数
inf>>kind;
long* t;
t=new long[kind];
long* coins;
coins=new long[kind];
long* c;
c=new long[kind];
for (i=0;i>t[i]>>coins[i];
long total=0,mincount=99999999,ccount=0;
inf>>total;
//计算
for (i=0;it[j])
{
Swap(t[i],t[j]);
Swap(coins[i],coins[j]);
}
}
long sum=0;
for (i=0;i0)&&(sum>=total))
for (i=kind-1;i>=0;i--)
{
Swap(t[i],t[kind-1]);
Swap(coins[i],coins[kind-1]);
if (t[kind-1]>0)
{
c[kind-1]=temptotal/t[kind-1];
if (c[kind-1]>=coins[kind-1])
c[kind-1]=coins[kind-1];
long tempcount=0;
while((c[kind-1]>0)&&(c[kind-1]<=mincount))
{
tempcount=c[kind-1];
temptotal=temptotal-t[kind-1]*c[kind-1];
for (j=kind-2;j>=0;j--)
if
((temptotal>0)&&(t[j]>0))
{
c[j]=temptotal/t[j];
if
(c[j]>=coins[j])
c[j]=coins[j];
temptotal=temptotal-t[j]*c[j];
tempcount=tempcount+c[j];
}
if
((tempcount>0)&&(tempcount
本文档为【最少硬币问题】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。