《算法笔记》——贪心算法

参考：

算法笔记 (豆瓣) (douban.com)

一、简单贪心

贪心法是求解一类最优化问题的方法，它总是考虑在当前状态下局部最优（或较优）的策略，来使全局的结果达到最优（或较优）。显然，如果采取较优而非最优的策略（最优策略可能不存在或是不易想到)，得到的全局结果也无法是最优的。而要获得最优结果，则要中间的每步策略都是最优的，因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法，即假设策略不能导致最优解，然后通过系列推导来得到矛盾，以此证明策略是最优的，最后用数学归纳法保证全局最优。不过对平常使用来说，也许没有时间或不太容易对想到的策略进行严谨的证明（贪心的证明往往比贪心本身更难)，因此一般来说，如果在想到某个似乎可行的策略，并且自己无法举出反例，那么就勇敢地实现它。

PAT 1020 月饼（25 分）

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。

样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45 / 2 = 94.5（亿元）。

输入格式：

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。

随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

输入样例：

1
2
3
3 20
18 15 10
75 72 45

输出样例：

1
94.50
代码长度限制 16 KB
时间限制 150 ms
内存限制 64 MB
栈限制 8192 KB

题解：

思路

步骤1：这里采用“总是选择单价最高的月饼出售，可以获得最大的利润”的策略。因此，对每种月饼，都根据其库存量和总售价来计算出该种月饼的单价。之后，将所有月饼按单价从高到低排序。

步骤2：从单价高的月饼开始枚举。

①如果该种月饼的库存量不足以填补所有需求量，则将该种月饼全部卖出，此时需求量减少该种月饼的库存量大小，收益值增加该种月饼的总售价大小。

②如果该种月饼的库存量足够供应需求量，则只提供需求量大小的月饼，此时收益值增加当前需求量乘以该种月饼的单价，而需求量减为 0。这样，最后得到的收益值即为所求的最大收益值。

策略正确性的证明：假设有两种单价不同的月饼，其单价分别为 a 和 b ( a < b )。如果当前需求量为 K，那么两种月饼的总收入分别为 aK 与 bK，而 aK < bK 显然成立，因此需要出售单价更高的月饼。

代码

这里的思路是差不多的，核心思路在于，如果当前所需 - 存量 >= 0，就可以进行 ans 累加，同时减去相应的存量；不然只需要累加 need 数量即可，然后需要跳出循环。

其他的需要注意的地方在于一些格式和输入的处理。

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
def max_profit(kind, need, stock, value):
    # 月饼单价
    unit_value = {i: value[i] / stock[i] for i in range(kind)}
    # 月饼顺序
    order = sorted(unit_value, key=lambda i:unit_value[i], reverse=True)

    ans = 0

    # 如果月饼需求量还有, 并且当前价值最大的月饼比所需的量大, 就卖出当前月饼
    for i in order:
        if need - stock[i] >= 0:
            ans += value[i]
            need -= stock[i]
        else:
            ans += need * unit_value[i]
            break
    return ans

# 种类和需求
kind, need = map(int, input().split())
# 月饼存量
stock = list(map(float, input().split()))
# 月饼价值
value = list(map(float, input().split()))

ans = max_profit(kind, need, stock, value)

print("{:.2f}".format(ans))
结果

PAT 1023 组个最小数（20 分）

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。

现给定数字，请编写程序输出能够组成的最小的数。

输入格式：

输入在一行中给出 10 个非负整数，顺序表示我们拥有数字 0、数字 1、……数字 9 的个数。整数间用一个空格分隔。10 个数字的总个数不超过 50，且至少拥有 1 个非 0 的数字。

输出格式：

在一行中输出能够组成的最小的数。

输入样例：

1
2 2 0 0 0 3 0 0 1 0

输出样例：

1
10015558
代码长度限制 16 KB
时间限制 200 ms
内存限制 64 MB
栈限制 8192 KB

题解：

策略是：先从 1 ~ 9 中选择个数不为 0 的最小的数输出，然后从 0 ~ 9 输出数字，每个数字输出次数为其剩余个数。 以样例为例，最高位为个数不为 0 的最小的数 1，此后 1 的剩余个数减 1（由 2 变为 1 ）。接着按剩余次数( 0 剩余两个，1 剩余一个，5 出现三个，8 出现一个)依次输出所有数。 策略正确性的证明：首先，由于所有数字都必须参与组合，因此最后结果的位数是确定的。然后，由于最高位不能为 0，因此需要从 [ 1 , 9 ] 中选择最小的数输出（如果存在两个长度相同的数的最高位不同，那么一定是最高位小的数更小)。最后，针对除最高位外的所有位，也是从高位到低位优先选择 [ 0 , 9 ] 中还存在的最小的数输出。

思路

这题的思路其实也是很清晰的，第一位数字需要特殊处理，最小的非 0 数字；

后续的数字，只要把数字列表从小到大排序，添加到后面即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 获得给定的数字个数
inputs = list(map(int, input().split()))

# 从小到大把所有数字依次添加到 nums
nums = list()
for i in range(10):
    for j in range(inputs[i]):
        nums.append(i)

ans = ""

# 添加第一个最小的非零数字
for num in nums:
    if num != 0:
        ans += str(num)
        # 从 nums 中删除这个数字（remove() 函数只删除第一个匹配的数字）
        nums.remove(num)
        break

# 按顺序把所有数字添加到 ans 即可
for num in nums:
    ans += str(num)

print(ans)
结果

二、区间贪心

区间贪心示例

通过上面的例子，读者可以对贪心有一个大致的了解。下面来看一个稍微复杂一点的问题，即区间不相交问题：给出 N 个开区间（x, y)，从中选择尽可能多的开区间，使得这些开区间两两没有交集。例如对开区间 (1, 3)、(2, 4)、(3, 5)、(6, 7) 来说，可以选出最多三个区间(1, 3)、(3, 5)、(6, 7)，它们互相没有交集。

首先考虑最简单的情况，如果开区间I被开区间 \(I_2\) 包含，如图 4-5 所示，那么显然选择 \(I_1\) 是最好的选择，因为如果选择，那么就有更大的空间去容纳其他开区间。接下来把所有开区间按左端点 x 从大到小排序，如果去除掉区间包含的情况，那么一定有 \(y_1\) > \(y_2\) > … > \(y_n\) 成立，如图 4-5 b 所示。现在考虑应当如何选取区间。通过观察会发现，\(I_1\) 的右边有一段是一定不会和其他区间重叠的，如果把它去掉，那么 \(I_1\) 的左边剩余部分就会被 \(I_2\) 包含，由图 4-5 a 的情况可知，应当选择 \(i_1\)。因此对这种情况，总是先选择左端点最大的区间(总是选择右端最小的区间也是可行的)。

区间不相交问题策略图

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def interval_greedy(_intervals):
    # 1. 按照结束时间对区间进行排序
    sorted_intervals = sorted(_intervals, key=lambda x: x[1])

    # 2. 选择第一个区间
    selected_intervals = []
    end_time = -float('inf')  # 上一个选择的区间的结束时间

    for interval in sorted_intervals:
        # 如果当前区间的开始时间大于等于上一个选择区间的结束时间，则选择该区间
        if interval[0] >= end_time:
            selected_intervals.append(interval)
            end_time = interval[1]  # 更新结束时间

    return selected_intervals


# 示例输入
intervals = [(1, 3), (2, 5), (4, 6), (6, 7), (5, 8)]
result = interval_greedy(intervals)
print("选择的区间:", result)

练习题

问题 A: 看电视

内存限制 时间限制
32 MB 1.000 S

题目描述

暑假到了，小明终于可以开心的看电视了。但是小明喜欢的节目太多了，他希望尽量多的看到完整的节目。 现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？

输入

输入包含多组测试数据。每组输入的第一行是一个整数 n（n <=1 00），表示小明喜欢的节目的总数。 接下来 n 行，每行输入两个整数 si 和 ei（1 <= i <= n），表示第 i 个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。 当 n = 0 时，输入结束。

输出

对于每组输入，输出能完整看到的电视节目的个数。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

样例输出

1
5

题解

思路

贪心策略：

将电视节目按照结束时间进行排序，每次选择结束时间最早的节目，这样保证有尽可能多的时间选择后续节目。

代码

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
32
33
34
35
36
37
38
"""
《算法笔记》4.4 简单贪心 问题 A 看电视
贪心策略：
    将电视节目按照结束时间进行排序，每次选择结束时间最早的节目，这样保证有尽可能多的时间选择后续节目
"""


def max_programs(_intervals):
    # 贪心策略：将电视节目按照结束时间进行排序，每次选择结束时间最早的节目，这样保证有尽可能多的时间选择后续节目
    sorted_intervals = sorted(_intervals, key=lambda x: x[1])

    ans = 0
    end_time = -float('inf')

    for interval in sorted_intervals:
        if interval[0] >= end_time:
            ans += 1
            end_time = interval[1]

    return ans


# 循环读取输入
while True:
    # 当 n 为 0 时，结束循环
    n = int(input())
    if n == 0:
        break

    # 读取电视节目
    programs = []
    for _ in range(n):
        start, end = map(int, input().split())
        programs.append((start, end))

    # 计算并输出结果
    ans = max_programs(programs)
    print(ans)

问题 B: 出租车费

内存限制 时间限制
32 MB 1.000 S

题目描述

某市出租车计价规则如下：起步 4 公里 10 元，即使你的行程没超过 4 公里；接下来的 4 公里，每公里 2 元；之后每公里 2.4 元。行程的最后一段即使不到 1 公里，也当作 1 公里计费。 一个乘客可以根据行程公里数合理安排坐车方式来使自己的打车费最小。 例如，整个行程为 16 公里，乘客应该将行程分成长度相同的两部分，每部分花费 18 元，总共花费 36 元。如果坐出租车一次走完全程要花费 37.2 元。 现在给你整个行程的公里数，请你计算坐出租车的最小花费。

输入

输入包含多组测试数据。每组输入一个正整数 n（n < 10000000），表示整个行程的公里数。 当 n = 0 时，输入结束。

输出

对于每组输入，输出最小花费。如果需要的话，保留一位小数。

样例输入

1
2
3
4
3
9
16
0

样例输出

1
2
3
10
20.4
36

题解

思路

贪心策略：

根据题目分析可以得到，8 km 是最便宜的，这里的贪心策略就是把行程划分为尽可能的 8 km 段，最后剩余的行程为 0 - 8 km；

如果是 0 - 4 km, 用 2.4 计算；

如果是 4 - 8 km, 用 10 + (x - 2) * 2 计算。

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
"""
《算法笔记》4.4 简单贪心 问题 B 出租车费

三段计费：
    1. x <= 4 km, 10 元
    2. 4 < x <= 8, 2 元/km
    3. x > 8, 2.4 元/km

贪心策略：
    根据题目分析可以得到，8 km 是最便宜的，这里的贪心策略就是把行程划分为尽可能
    的 8 km 段，最后剩余的行程为 0 - 8 km；
    如果是 0 - 4 km, 用 2.4 计算；
    如果是 4 - 8 km, 用 10 + (x - 2) * 2 计算。
"""


def min_cost(n):
    _ans = 0

    if n <= 4:
        # 当路程为 0 - 4 km
        _ans += 10
    elif n <= 8:
        # 当路程为 4 - 8 km
        _ans += 10 + (n - 4) * 2
    else:
        # 当路程 > 8 km, 按照 8 km 进行分段
        _ans += int(int(n) / 8) * 18;
        n %= 8

        # 剩余不足 8 km 的部分分两段：
        # < 4 km, 用 2.4 km 算
        # 4 - 8 km, 用 10 + (x - 2) * 2 算
        if 0 < n <= 4:
            # 如果剩余行程 <= 4，当作 2.4 来算
            _ans += n * 2.4
        elif 4 < n < 8:
            # 如果剩余行程 4 < x <= 7, 当作 10 + 2 来算
            _ans += 10 + (n - 4) * 2

    return _ans


while True:
    # 输入公里数, 0 退出循环
    distance = int(input())
    if distance == 0:
        break

    # 对于每个公里数，都进行计算
    ans = min_cost(distance)
    # 根据结果格式化输出
    print("{:.1f}".format(ans) if isinstance(ans, float) else ans)
#Python #贪心 #PTA
《算法笔记》——贪心算法
https://excelius.xyz/《算法笔记》——贪心算法/
作者
Excelius
发布于
2025年1月6日
许可协议