数据结构和算法-贪婪算法

sele

1、算法名称：贪婪算法
2、算法思路：
　　从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法中某一步不能再向前继续前进时，就停止算法，给出近似解
3、该算法存在的主要问题
1、不能保证最后的解释最优的
2、不能用来求最大或最小解的问题
３、只能求满足某些约束条件的可行解的范围
4、实例：
　　在买东西找零钱的时候，有多种找零钱的方式可以采取。如果按照贪婪算法是按照面值由大到小的顺序来找零的、

代码：

• #include<stdio.h>
  
• #define MAXN 9
  
• int parvalue[MAXN]={10000,5000,1000,500,200,100,50,20,10};
  
• int num[MAXN]={0};
  
• int exchange(int n)
  
• {
  
• 
  
•     int i,j;
  
•     for(i=0;i<MAXN;i++)
  
•         if(n>parvalue) break;//找到比n小的最大面额
  
•     while(n>0&&i<MAXN)
  
•     {
  
• 
  
•         if(n>=parvalue)
  
•         {
  
• 
  
•             n-=parvalue;
  
•             num++;
  
•         }else
  
•         {
  
•             if(n<10&&n>=5)
  
•             {
  
•                 num[MAXN-1]++;
  
•                 break;
  
•             }else i++;
  
•         }
  
•     }
  
•     return 0;
  
• }
  
• int main()
  
• {
  
•   int i;
  
•   float m;
  
•   printf("请输入找零的金额");
  
•   scanf("%f",&m);
  
•   exchange((int)100*m);
  
•   printf("\n%0.2f元零钱的组成 \n",m);
  
•   for(i=0;i<MAXN;i++)
  
•       if(num>0)
  
•         printf("%6.2f: %d张\n",(float)parvalue/100.0,num);
  
•   getch();
  
•   return 0;
  
• }
  

　　程序运行结果



附件列表