守望者--AIR技术交流

标题: 编程算法之贪婪算法 [打印本页]
作者: yaoyuan0701    时间: 2015-4-21 21:53
标题: 编程算法之贪婪算法
贪婪算法并不从整体最优考虑，它所作出的选择只是局部最优选择。
贪婪算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解，当达到算法中的某一步不能再继续前进时，就前进该算法。
该算法可能存在以下几个问题：
不能保证最后的解是最优的
不能用来求最大或者最小问题
不能求满足某些约束条件可行解的范围。


例如：在超市购物，收银员要给顾客找零，怎么才能求出找出零钱的最优算法呢？

  1.     // 编程算法之贪婪法.cpp : 定义控制台应用程序的入口点。  
  2.     //  
  3.       
  4.     #include "stdafx.h"  
  5.     #define MAXN 10  
  6.       
  7.     int parvalue[MAXN] = {10000,5000,2000,1000,500,200,100,50,20,10};  
  8.       
  9.     int num[MAXN] = {0};  
  10.       
  11.     int exchange(int n)  
  12.     {  
  13.         int i,j;  
  14.         for (i = 0; i < MAXN; i++)  
  15.         {  
  16.             if(n>parvalue[i])  
  17.             {  
  18.                 break;  
  19.             }  
  20.         }  
  21.         while (n>0 && i<MAXN)  
  22.         {  
  23.             if(n>=parvalue[i])  
  24.             {  
  25.                 n-=parvalue[i];  
  26.                 num[i]++;  
  27.                   
  28.             }  
  29.             else if(n<10 && n>=5)  
  30.             {  
  31.                 num[MAXN-1] ++;  
  32.                 break;  
  33.             }  
  34.             else  
  35.             {  
  36.                 i++;  
  37.             }  
  38.         }  
  39.         return 0;  
  40.     }  
  41.       
  42.       
  43.       
  44.     int _tmain(int argc, _TCHAR* argv[])  
  45.     {  
  46.         int i;  
  47.         float m;  
  48.         printf("请输入找零的金额：");  
  49.         scanf_s("%f",&m);  
  50.         exchange(int(100*m));  
  51.         for(i=0;i<MAXN;i++)  
  52.         {  
  53.             if (num[i]>=1)  
  54.             {  
  55.                   
  56.                 printf("%6.2f:%d张\n",(float)parvalue[i]/100.0,num[i]);  
  57.       
  58.             }  
  59.         }  
  60.         return 0;  
  61.     }  
复制代码
http://blog.csdn.net/yaoyuan0701/article/details/45157543




欢迎光临 守望者--AIR技术交流 (http://www.airmyth.com/)