贪心算法介绍-知识专区-汉码未来

当前位置： Python > 贪心算法介绍

admin · 更新于 2021-08-06

1. 贪心算法介绍

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

2. 贪心算法思路介绍

对于贪心算法，其实现思路一般如下：

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

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

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

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

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

4. 贪心算法的典型应用

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

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

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

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

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

$ts[i]￥：表示第 i 个宝物的价值 $i = 1 . . . n$ ；
$w s [i]$ ：表示第 i 个宝物的重量 $i = 1 . . . n$ ；
$t$ ：表示毛驴最大运载能力。

此时我们需要计算宝物的单位价值：
$pre\_value[i]=\frac{ts[i]}{ws[i]},i=1,\cdots,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)代码块
1
2
3
4
5

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

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代码块
1
2
3
4
5
6
7
8
9
10

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

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 wif __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)))代码块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31