守望者--AIR技术交流

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: ANE FlasCC 炼金术
查看: 888|回复: 0

[技术资料] 编程算法之贪婪算法

[复制链接]
  • TA的每日心情
    慵懒
    2015-4-16 10:25
  • 签到天数: 8 天

    [LV.3]偶尔看看II

    18

    主题

    19

    帖子

    1284

    积分

    版主

    Rank: 16Rank: 16Rank: 16Rank: 16

    威望
    11
    贡献
    0
    金币
    359
    钢镚
    20
    发表于 2015-4-21 21:53:31 | 显示全部楼层 |阅读模式
    贪婪算法并不从整体最优考虑,它所作出的选择只是局部最优选择。
    贪婪算法的基本思路:从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的求得更好的解,当达到算法中的某一步不能再继续前进时,就前进该算法。
    该算法可能存在以下几个问题:
    不能保证最后的解是最优的
    不能用来求最大或者最小问题
    不能求满足某些约束条件可行解的范围。


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

    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

    评分

    参与人数 1威望 +1 收起 理由
    破晓 + 1

    查看全部评分

    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    
    关闭

    站长推荐上一条 /4 下一条

    QQ|手机版|Archiver|网站地图|小黑屋|守望者 ( 京ICP备14061876号

    GMT+8, 2019-11-16 00:19 , Processed in 0.041233 second(s), 33 queries .

    守望者AIR

    守望者AIR技术交流社区

    本站成立于 2014年12月31日

    快速回复 返回顶部 返回列表