贪心算法介绍

接下来的三个小节内容我们将介绍基础算法中的一个经典算法:贪心算法。贪心算法比较直观,有时候能很好的解决问题,但有时候求出的结果非最优解。所以在使用贪心算法时一定要对其应用场景以及相应的问题掌握清楚,方能在算法题解中游刃有余。

1. 贪心算法介绍

所谓贪心算法是指在对问题求解时,总是选择在当前看来是最好的方法。即从局部考察最优而非整体。贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是:贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性 (即某个状态以后的过程不会影响以前的状态,只与当前状态有关)。 所以,对所采用的贪心策略一定要仔细分析其是否满足无后效性。

2. 贪心算法思路介绍

对于贪心算法,其实现思路一般如下:

• 建立数学模型来描述问题;
• 把求解的问题分成若干个子问题;
• 对每个子问题求解,得到子问题的局部最优解;
• 把子问题的解局部最优解合成原来问题的一个解。

3. 要不要使用贪心算法?

使用贪心算法在很多问题上不一定能求得最优解,因此我们再使用贪心算法时需要严格思考使用贪心的策略能否达到我们想要的结果。贪心策略适用的前提是:局部最优策略能导致产生全局最优解。实际上,贪心算法适用的情况很少,一般对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可以做出判断。

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即当考虑做何种选择的时候,我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

在介绍完贪心相关的概念、实现思路、缺陷以及相关适用场景后,我们介绍一个关于贪心算法的典型应用场景,帮助我们更好的理解贪心的实现,便于后面完成相应的题解。

4. 贪心算法的典型应用

这是一个非常经典的编程题,题名为:洞中取宝,题目的描述如下:

假设山洞中有 n 种宝物,每种宝物有一定重量 w 和相应的价值 v,毛驴运载能力有限,只能运走 m 重量的宝物,一种宝物只能拿一样,宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢?

注意:由于宝物有重量和价值两种特征,我们的贪心是应该取价值还是重量呢?还是二者兼顾?这样会产生三种贪心策略:

• 每次挑选价值最大的宝物,直到无法运载下一个宝物为止;
• 每次挑选重量最轻的宝物,直到无法运载下一个宝物为止;
• 每次挑选价值/重量 最大的宝物,直到无法运载下一个宝物为止;

很明显,我们贪心的策略应该选择第三种,这样能兼顾宝物价值和重量,找到满足要求的最优解:

• $ts[i]\:表示第 i 个宝物的价值 $i=1...n$i=1...n;
• $ws[i]$ws[i]:表示第 i 个宝物的重量 $i=1...n$i=1...n;
• $t$t:表示毛驴最大运载能力。

此时我们需要计算宝物的单位价值:
$pre\_value[i]=\frac{ts[i]}{ws[i]},i=1,\cdots,n$pre_value[i]=ws[i]ts[i]​,i=1,⋯,n

5. 贪心算法的 Python 代码实现

有了宝物的单位价值之后,接下来我们需要对宝物按照单位价值进行排序,使用 python 自带的 sort 方法即可。注意要保持宝物的价值和总量一起变化,所以需要将宝物的重量、价值以及单位价值作为一个整体,然后进行排序:

pre_value = []
for i in range(len(ts)):
 pre_value.append([ts[i], ws[i], ts[i] / ws[i]])
# 按照单位价值从大到小进行排序
pre_value.sort(key=lambda d: d[2], reverse=True)

接下来就是按照贪心算法从大到小选择,直到宝物价值超出剩余的运载价值,然后将宝物切割带走:

for i in range(len(pre_value)):
 if pre_value[i][1] <= t:
 # 从大到小开始装
 w += pre_value[i][0]
 # 每装一个运载能力减去宝物重量
 t -= pre_value[i][1]
 else:
 # 可以取走宝物的一部分,达到最大装载
 w += pre_value[i][2] * t
 break

整体给出洞中取宝问题的贪心实现,如下:

def get_treasures(ts, ws, t):
 """ 
 ts: 宝物价值
 ws: 宝物重量
 t:最大运载能力
 """
 
 w = 0
 # 计算宝物的性价比
 pre_value = []
 for i in range(len(ts)):
 pre_value.append([ts[i], ws[i], ts[i] / ws[i]])
 # 将宝物按单位价值从大到小进行排序
 pre_value.sort(key=lambda d: d[2], reverse=True)
 for i in range(len(pre_value)):
 if pre_value[i][1] <= t:
 w += pre_value[i][0]
 t -= pre_value[i][1]
 else:
 # 可以取走宝物的一部分,达到最大装载
 w += pre_value[i][2] * t
 break
 return w
if __name__ == '__main__':
 ts = [4, 2, 9, 5, 5, 8, 5, 4, 5, 5]
 ws = [3, 8, 18, 6, 8, 20, 5, 6, 7, 15]
 t = 30
 print("运走宝物的最大价值为:{}".format(get_treasures(ts, ws, t)))

还有许多类似的问题,如背包问题、最优装载问题、教室调度问题等等,都可以使用贪心算法解决。但是我们一定要找对贪心的值,这样才能确保得到最优的解。

6. 小结

本小节我们主要介绍了贪心算法以及相应的解题方式。接着介绍了贪心算法的一个典型应用,同时也指出了贪心算法在一些问题上的问题,比如无法得到最优解等。本小节主要是理解贪心算法以及掌握解题思路,接下来的两小节将进入实战训练,彻底理解和掌握贪心算法。