贪心算法找零钱

 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("找不开!
");
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("
");
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 }
View Code
贪心算法 找零钱

贪心算法找零钱
