贪心算法找零就是现实中从最大面额开始找的思路。不代表是最优解,只是算法之一。
由于面额输入顺序不定,我先对输入的面额进行降序排序。
下面代码:
#include <stdio.h>
#include <malloc.h>
int main()
{
int i,j,m,n,*ns=NULL,*cn=NULL,sum=0
printf("请输入总金额m及零钱种类n:"),scanf("%d",&m),scanf("%d",&n)
printf("请分别输入%d种零钱的面额:\n",n)
if(!(ns=(int *)malloc(sizeof(int)*n))) return 1
if(!(cn=(int *)malloc(sizeof(int)*n))) return 1
for(i=0i<ni++) scanf("%d",&ns[i])
//------------考虑输入面额顺序不定,先对面额进行降序排列(如按照降序输入,该段可删除)
for(i=0i<ni++)
for(j=i+1j<nj++)
if(ns[j]>ns[i]) ns[j]^=ns[i],ns[i]^=ns[j],ns[j]^=ns[i]
//-------------------------------------------------------------------
for(i=0i<ni++)//贪心算法,从最大面额开始
if(m>=ns[i])
cn[i]=m/ns[i],m=m%ns[i],sum+=cn[i],printf("%d元%d张 ",ns[i],cn[i])
printf("\n最少使用零钱%d张\n",sum)
return 0
}
#include <stdio.h>int main()
{
int a,b,c,d,e,t
scanf("%d",&t)
a=t%100
t-=a*100
if(a>0) printf("10元%d个 ", a)
b=t%50
t-=b*50
if(b>0) printf("5元%d个 ", b)
c=t%10
t-=c*10
if(c>0) printf("1元%d个 ", c)
d=t%5
t-=d*5
if(d>0) printf("5角%d个 ", d)
e=t
if(e>0) printf("1角%d个 ", e)
printf("\n")
return 0
}
double iChange=0double taget=0.72
double Money[5] = { 0.5, 0.1, 0.05, 0.02, 0.01}
double ArrChange[100]
for语句将ArrChange置零
int CountCoin=0
while(iChange != taget )
{
for(int i = 0 i <5 i ++)
{
if(iChange + Money[i] >taget)continue
else
{
iChange += Money[i]
ArrChange[CountCoin] = Money[i]
CountCoin++
}
}
}
//基本是这么个思路,如果一点也不思考对你没好处,原理就是找多了就换小的,尽量选大的钱