- 积分
- 1284
- 注册时间
- 2014-12-29
- 最后登录
- 2016-11-14
- 在线时间
- 17 小时
- 威望
- 11
- 贡献
- 0
- 金币
- 359
- 钢镚
- 20
- 交易凭证
- 0
- 分享
- 0
- 精华
- 0
- 帖子
- 19
- 主题
- 18
TA的每日心情 | 慵懒 2015-4-16 10:25 |
---|
签到天数: 8 天 [LV.3]偶尔看看II
版主
- 威望
- 11
- 贡献
- 0
- 金币
- 359
- 钢镚
- 20
|
贪婪算法并不从整体最优考虑,它所作出的选择只是局部最优选择。
贪婪算法的基本思路:从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的求得更好的解,当达到算法中的某一步不能再继续前进时,就前进该算法。
该算法可能存在以下几个问题:
不能保证最后的解是最优的
不能用来求最大或者最小问题
不能求满足某些约束条件可行解的范围。
例如:在超市购物,收银员要给顾客找零,怎么才能求出找出零钱的最优算法呢?
- // 编程算法之贪婪法.cpp : 定义控制台应用程序的入口点。
- //
-
- #include "stdafx.h"
- #define MAXN 10
-
- int parvalue[MAXN] = {10000,5000,2000,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[i])
- {
- break;
- }
- }
- while (n>0 && i<MAXN)
- {
- if(n>=parvalue[i])
- {
- n-=parvalue[i];
- num[i]++;
-
- }
- else if(n<10 && n>=5)
- {
- num[MAXN-1] ++;
- break;
- }
- else
- {
- i++;
- }
- }
- return 0;
- }
-
-
-
- int _tmain(int argc, _TCHAR* argv[])
- {
- int i;
- float m;
- printf("请输入找零的金额:");
- scanf_s("%f",&m);
- exchange(int(100*m));
- for(i=0;i<MAXN;i++)
- {
- if (num[i]>=1)
- {
-
- printf("%6.2f:%d张\n",(float)parvalue[i]/100.0,num[i]);
-
- }
- }
- return 0;
- }
复制代码 http://blog.csdn.net/yaoyuan0701/article/details/45157543
|
评分
-
查看全部评分
|