贪心/贪婪算法

目录

• 一、贪心算法的基本定义和特点
• 二、贪心算法的基本步骤
• 三、实例分析

---

一、贪心算法的基本定义和特点

• 贪心算法的英文是greedy algorithm，又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

• 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

• 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

• 贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。 由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情况，选择最优的解，可能会导致辛普森悖论（Simpson’s Paradox），不一定出现最优的解。

二、贪心算法的基本步骤

1. 步骤1：从某个初始解出发；

2. 步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；

3. 步骤3：将所有解综合起来。

三、实例分析

1.问题

换酒问题题目：
小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。
如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。
请你计算最多能喝到多少瓶酒？

2.例子与分析

• 示例 1
  输入：numBottles = 9, numExchange = 3 输出：13
  解释：你可以用 3 个空酒瓶兑换 1 瓶酒。喝完9瓶酒后（得到9个空瓶）可以兑换得到3瓶酒，再喝完这3瓶酒后（得到3个空瓶）又能兑换得到1瓶酒。所以最多能喝到 9 + 3 + 1 = 13 瓶酒。

• 示例 2
  输入：numBottles = 15, numExchange = 4 输出：19
  解释：你可以用 4 个空酒瓶兑换 1 瓶酒。所以最多能喝到 15 + 3 + 1 = 19 瓶酒。喝完15个瓶酒后（得到15个空瓶）可以兑换3瓶酒（此时剩余3个空瓶）；喝完这3瓶酒后（得到3个空瓶，此时剩余3+3=6个空瓶）又能兑换1瓶酒（此时剩余2个空瓶）；喝完这1瓶酒后（得到1个空瓶，此时剩余1+2=3个空瓶），手上的空瓶不足以兑换出一瓶酒，停止。
  

• 分析
  这道题贪心的维度非常明显，直接暴露在题目表面，即当前喝完所有饮料后变为空瓶加上已有空瓶后，最大限度的、贪心的兑换饮料，依次类推，直到手上的空瓶不足以兑换出一瓶饮料止。

3.代码编写（MATLAB版贪心算法）

% greedy algorithm(GA)贪心/贪婪算法

%购入了 numBottles 瓶酒
num_bottles = input('please input the number of bottles:');
%用 numExchange 个空酒瓶可以兑换一瓶新酒
num_exchange = input('please input the number of exchange:');

%初始化
sumb = num_bottles;  % 喝到酒的数目
empty = num_bottles;  % 空瓶数目

%贪心：当前喝完所有饮料后变为空瓶加上已有空瓶后，最大限度的、贪心的兑换饮料，依次类推，
% 直到手上的空瓶不足以兑换出一瓶饮料止。

while fix(empty / num_exchange) ~= 0 
    % fix函数用于取整数商，表示当前空瓶还能兑换酒时：进入循环；否则不足以兑换酒：循环退出
    bottle = fix(empty / num_exchange);  % 利用当前空瓶最大限度地兑换酒，得到当前酒的数目
    sumb = sumb + bottle;  % 更新喝到酒的数目
    empty = mod(empty,num_exchange) + bottle; %更新空瓶数目:空瓶=兑换后剩余空瓶+兑换得到的酒瓶
end

sumb %最终喝到酒的瓶数