江苏龙网

  1. 主页 > 生活百科 > >

贪心算法简介

贪婪算法

贪婪算法贪心算法（Greedy Algorithm) 简介贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解 。{看着这个名字，贪心，贪婪这两字的内在含义最为关键 。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉 。}
贪婪法的基本步骤：步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来 。
事例一：找零钱问题假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？这里需要明确的几个点：1.货币只有 25 分、10 分、5 分和 1 分四种硬币；2.找给客户 41 分钱的硬币；3.硬币最少化思考，能使用我们今天学到的贪婪算法吗？怎么做？（回顾一下上文贪婪法的基本步骤，1，2，3）

  1. 找给顾客sum_money=41分钱，可选择的是25 分、10 分、5 分和 1 分四种硬币 。能找25分的，不找10分的原则，初次先找给顾客25分；
  2. 还差顾客sum_money=41-25=16 。然后从25 分、10 分、5 分和 1 分四种硬币选取局部最优的给顾客，也就是选10分的，此时sum_money=16-10=6 。重复迭代过程，还需要sum_money=6-5=1,sum_money=1-1=0 。至此，顾客收到零钱，交易结束；
  3. 此时41分，分成了1个25，1个10，1个5，1个1，共四枚硬币 。
编程实现
#include<IOStream>using namespace std;#define ONEFEN1#define FIVEFEN5#define TENFEN10#define TWENTYFINEFEN 25int main(){int sum_money=41;int num_25=0,num_10=0,num_5=0,num_1=0;//不断尝试每一种硬币while(money>=TWENTYFINEFEN) { num_25++; sum_money -=TWENTYFINEFEN; }while(money>=TENFEN) { num_10++; sum_money -=TENFEN; }while(money>=FIVEFEN){ num_5++;sum_money -=FIVEFEN; }while(money>=ONEFEN){ num_1++;sum_money -=ONEFEN; }//输出结果cout<< "25分硬币数："<<num_25<<endl;cout<< "10分硬币数："<<num_10<<endl;cout<< "5分硬币数："<<num_5<<endl;cout<< "1分硬币数："<<num_1<<endl;return 0;}事例二:背包最大价值问题有一个背包，最多能承载重量为 C=150的物品，现在有7个物品（物品不能分割成任意大小），编号为 1~7，重量分别是 wi=[35,30,60,50,40,10,25]，价值分别是 pi=[10,40,30,50,35,40,30]，现在从这 7 个物品中选择一个或多个装入背包，要求在物品总重量不超过 C 的前提下，所装入的物品总价值最高 。这里需要明确的几个点：
  1. 每个物品都有重量和价值两个属性；
  2. 每个物品分被选中和不被选中两个状态（后面还有个问题，待讨论）；
  3. 可选物品列表已知，背包总的承重量一定 。
所以，构建描述每个物品的数据体结构 OBJECT和背包问题定义为
//typedef是类型定义的意思//定义待选物体的结构体类型typedef struct tagObject{int weight;int price;int status;}OBJECT;//定义背包问题typedef struct tagKnapsackProblem{vector<OBJECT>objs;int totalC;}KNAPSACK_PROBLEM;这里采用定义结构体的形式，主要是可以减少代码的书写量,可以实现代码的复用性和可扩展性,简化，提高可读性 。就是贪图简单方便，规避繁琐 。
如下,实例化
objectsOBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 },{ 40,35,0 },{ 10,40,0 },{ 25,30,0 } };思考：如何选，才使得装进背包的价值最大呢？
策略1：价值主导选择，每次都选价值最高的物品放进背包；
策略2：重量主导选择，每次都选择重量最轻的物品放进背包；
策略3：价值密度主导选择，每次选择都选价值/重量最高的物品放进背包 。
（贪心法则：求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好或最优的解）
策略1：价值主导选择，每次都选价值最高的物品放进背包根据这个策略最终选择装入背包的物品编号依次是 4、2、6、5，此时包中物品总重量是 130，总价值是 165 。
//遍历没有被选的objs,并且选择price最大的物品,返回被选物品的编号int Choosefunc1(std::vector<OBJECT>& objs, int c){int index = -1;//-1表示背包容量已满int max_price = 0;//在objs[i].status == 0的物品里，遍历挑选objs[i].price最大的物品for (int i = 0; i < static_cast<int>(objs.size()); i++){if ((objs[i].status == 0) && (objs[i].price > max_price ))//objs没有被选,并且price> max_price{max_price= objs[i].price;index = i;}}return index;}


推荐阅读


上一篇：nginx注册成windows服务的解决方法

下一篇：今年高端安溪铁观音秋茶收购价上涨至两成