数据酷学 | 贪心算法
数据酷学
贪心算法
01
引言
何为“贪心”？
“做出局部最优选择，来构造全局最优。”
“我们直接做出在当前问题看来最优的选择，而不必考虑子问题的解。”
——《算法导论 第3版》
事实上，贪心算法中的局部选择是独立、不依赖将来的选择。
02
贪心策略的过程
其一般步骤为：
·应用当前“最优”的目标作为统一目标
·原问题化为一个相似的但规模更小的子问题
·每一步选出来的是原问题最优解的一部分
·只剩一个子问题 #（完成）
03
例1：最少的箭数扎气球
问题描述：
对于一些给定x(start)和x(end)——即气球的直径范围的气球，如何用最少的箭数扎爆所有气球？
问题形象化：
贪心策略：
1. 初始化x0=points[0][0]，此时打掉y0个气球
2. 移动 x0—— one for each
移动至x1,新增一个可射气球。（保证原来可以被射的还能被射）
3. 至x2，同理。
4. 至x3，再往右射箭，可射气球数减少——不够贪心。
5. 终止，射箭！
6. 准备新箭，开始下一轮。repeat #
其中，最重要的是每次都要更新最小右边界，从而达到我们的贪心策略，这步的代码如下：
04
例2：国王庆典游戏
恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
问题形象化：
我们会发现：交换或许是控制贪心策略的关键，因为只影响交换者的奖金收益。
在这个问题中，制定贪心策略的关键在于，利用上述规律推导出这个例子下我们应满足的数学表达式，其具体推导如下图所示：
05
题外话：注意要有良好的编程风格
看看下面这个图示，我们有一些花盆，上面可能有花，可能没有：
如果对上述例子我们编写程序，直接运用if-else一顿干：
if(flowerbed[0]==1) //如果这一个花盆有花
{
if(n==1)
{
return false;
}
if(n==0)
{
return true;
}
}
if(flowerbed[0]==0) //如果这一个花盆没花
{
return true;
}
我们可以想到整型和布尔型的强制转换，利用逻辑运算来表达，也就是：
if(size==1)
return !((bool)flowerbed[0]&&(bool)n);
这下程序只需一行就可以达意，太优雅！老亮看了都说赞！
小结
贪得功成
心有余而力不足
算海无涯苦作舟
法至则必得！
参考文献：
1、《算法导论 第3版》
Thomas H.Cormen / Charles E.Leiserson / Ronald L.Rivest / Clifford Stein
译者:
殷建平 / 徐云 / 王刚 / 刘晓光 / 苏明 / 邹恒明 / 王宏志
今天的小知识就到这儿啦
下周一锁定SUIBE数据科学系
我们继续与你分享专业小知识！
关注
把握
第一手知识和讯息
内容制作|胡思劼
图文排版|张康晨
内容审核|葛飞翔