贪心算法找零钱

80 阅读 0 评论 53 点赞

我是靠谱客的博主哭泣大碗，最近开发中收集的这篇文章主要介绍贪心算法找零钱，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

 1 #include<stdio.h>
 2 #define N 60
 3 int exchage(float n,float *a,int c,float *r);
 4 void main()
 5 {
 6
float rmb[]={100,50,20,10,5,2,1,0.5,0.2,0.1};
 7
int n=sizeof(rmb)/sizeof(rmb[0]),k,i;
 8
float change,r[N];;
 9
printf("请输入要找的零钱数:");
10
scanf("%f",&change);
11
for(i=0;i<n;i++)
12
if(change>=rmb[i])
13
break;
14
k=exchage(change,&rmb[i],n-i,r);
15
if(k<=0)
16
printf("找不开!n");
17
else
18 
{
19
printf("找零钱的方案:%.2f=",change);
20
if(r[0]>=1.0)
21
printf("%.0f",r[0]);
22
else
23
printf("%.2f",r[0]);
24
for(i=1;i<k;i++)
25 
{
26
if(r[i]>=1.0)
27
printf("+%.0f",r[i]);
28
else
29
printf("+%.2f",r[i]);
30 
}
31
printf("n");
32 
}
33 }
34 int exchage(float n,float *a,int c,float *r)
35 {
36
int m;
37
if(n==0.0)
/*能分解，分解完成*/
38
return 0;
39
if(c==0)
/*不能分解*/
40
return -1;
41
if(n<*a)
42
return exchage(n,a+1,c-1,r);
/*继续寻找合适的面值*/
43
else
44 
{
45
*r=*a;
/*将零钱保存到r中*/
46
m=exchage(n-*a,a,c,r+1);
/*继续分解剩下的零钱*/
47
if(m>=0)
48
return m+1;
/*返回找零的零钱张数*/
49
return -1;
50 
}
51 }