推荐软件产品
twitter,facebook,ins,youtube视频下载
磨针音视频转文字
磨针免费pdf转word
磨针微信定时发文件和消息
磨针c盘清理，任何场景都能释放几十G的空间

定义

贪心算法，又名贪婪法，是寻找最优解问题的常用方法（其实得到的往往是近似最优解），这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。

基本步骤

• 步骤 1：从某个初始解出发；
• 步骤 2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
• 步骤 3：将所有解综合起来。

实例：找零钱问题

假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？

分析步骤

问题的解的限制条件为个数最少，符合寻找最优解问题的特征

分解问题：取一个硬币，使用贪心策略，为了使总硬币个数最少，硬币取尽可能最大面额的，然后计算剩余找零额

对上述子问题迭代，得到最优解

代码实现

#include<iostream>
using namespace std;

#define ONEFEN    1
#define FIVEFEN    5
#define TENFEN    10
#define TWENTYFINEFEN 25

int main()
{
  int sum_money=41;
  int num_25=0,num_10=0,num_5=0,num_1=0;

  //不断尝试每一种硬币
  while(sum_money>=TWENTYFINEFEN) { num_25++; sum_money -=TWENTYFINEFEN; }
  while(sum_money>=TENFEN) { num_10++; sum_money -=TENFEN; }
  while(sum_money>=FIVEFEN)  { num_5++;  sum_money -=FIVEFEN; }
  while(sum_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;
}

扩展：最优解

将问题中的硬币种类改为 25 分、20 分、10 分、5 分和 1 分五种硬币，找零额依然为 41 分

此时使用贪心算法得到结果与原问题相同：25 分 1 枚，10 分 1 枚，5 分 1 枚，1 分 1 枚，共 4 枚

但该解并非最优解，最优解为：20 分 2 枚，1 分 1 枚，共 3 枚

可以看出贪心算法的局限性是不能得到确定的全局最优解，但优点就是速度快且占用资源少