ACM 算法入门 · 贪心篇：从局部最优到整体最优的策略思维

什么是贪心算法？

贪心算法（Greedy Algorithm） 是一种在每一步选择中都采取当前状态下最优（即最有利）选择的策略，期望通过局部最优最终达到全局最优。

它的核心思想是：

局部最优 ➜ 全局最优

但需要特别注意的是：贪心策略并不总是适用于所有问题，它只适合满足以下两个条件的问题：

  • ✅ 最优子结构：问题的最优解包含其子问题的最优解；
  • ✅ 无后效性：某一步的选择不会影响后续的选择过程。

如果问题不满足这两个性质，使用贪心算法可能得不到正确解。

贪心算法的基本思路

贪心算法虽然没有统一的模板，但通常遵循以下解决步骤：

  1. 建立数学模型：用合理的数据结构和变量表达问题；
  2. 拆解为子问题：将原问题划分为一系列阶段性子问题；
  3. 定义贪心策略：找出每一步的“最优选择”规则；
  4. 按策略求解子问题：每次都按照贪心策略做选择；
  5. 组合局部最优解：最终汇总各步的选择，构成整体解。

贪心算法存在的问题

  • 不能保证最终求得的解一定是全局最优；
  • 不适用于所有需要求最大值或最小值的问题；
  • 只能求满足某些特定约束条件下的可行解。

贪心算法适用的问题

贪心算法适用的前提是：局部最优策略能够导致全局最优解。
实际上，适用场景较少。判断一个问题是否适合贪心算法，通常可以通过实际数据测试和理论分析来确定。

贪心选择性质

  • 贪心选择性质：问题的整体最优解可通过一系列局部最优选择构建。
    换言之，在做每一步选择时，只关注当前问题的最优选择，不考虑后续子问题的解。

  • 贪心算法通过迭代进行，每次选择都会简化问题规模，形成更小的子问题。

  • 最优子结构性质：问题的最优解包含其子问题的最优解。
    这是贪心算法能正确求解问题的关键。

贪心算法的实现框架

1
2
3
4
5
6
从初始解开始：
while (未达到目标) {
    根据贪心策略选择当前最优的决策；
    将该决策加入解中，简化问题规模；
}
最终，所有决策组合成问题的一个可行解。

✨ 示例：找零钱问题

目标：用尽量少的硬币凑出某个金额
硬币面额：25 分、10 分、5 分、1 分
贪心策略：每次选择当前面值最大的硬币

1
2
3
4
5
6
7
8
9
10
11
def greedy_coin_change(amount):
    coins = [25, 10, 5, 1]
    res = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            res.append(coin)
    return res

print(greedy_coin_change(63))  # 输出：[25, 25, 10, 1, 1, 1]

贪心策略：每次优先选面值最大的硬币。

选择步骤：

  • 63 分 ——> 选择 2 个 25 分硬币，剩余 63 - 50 = 13 分

  • 13 分 ——> 选择 1 个 10 分硬币，剩余 13 - 10 = 3 分

  • 3 分 ——> 选择 0 个 5 分硬币（3 分不足 5 分），剩余 3 分

  • 3 分 ——> 选择 3 个 1 分硬币，剩余 3 - 3 = 0 分，完成！

硬币组合：25 分 × 2 + 10 分 × 1 + 1 分 × 3 = 63 分

1
2
3
4
5
6
7
8
9
10
11
12
13
[63元]
  |
  v
[用25元硬币×2] ---> [剩余13元]
                          |
                          v
                  [用10元硬币×1] ---> [剩余3元]
                                      |
                                      v
                            [用5元硬币? 不够]
                                      |
                                      v
                            [用1元硬币×3] ---> [剩余0元，完成]

贪心算法经典算法题

背包问题

题目：
有一个背包，容量为 M = 150，有 7 个物品，物品可分割成任意大小。
要求尽可能使装入背包的物品总价值最大，但不能超过总容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30

目标与约束

  • 目标函数：最大化总价值 ( \sum p_i )
  • 约束条件：总重量不超过背包容量
∑wi≤M(M=150) \sum w_i \leq M \quad (M=150)

贪心策略分析

针对该问题，考虑三种贪心策略：

  1. 每次选择价值最高的物品装入背包
  2. 每次选择重量最小的物品装入背包
  3. 每次选择单位重量价值最高的物品装入背包

策略有效性探讨

  • 策略 1：选择价值最大物品
    不一定最优。
    反例：

    • 容量 ( W=30 )
    • 物品：A(28kg,30 价), B(12kg,20 价), C(12kg,20 价)
      该策略先选 A，背包剩余空间不足以选 B 和 C。但选 B 和 C 总价值 40，优于选 A 的 30。

  • 策略 2：选择重量最小物品
    同样不一定最优，类似策略 1 的反例适用。

  • 策略 3：选择单位重量价值最高物品
    是解决分数背包的经典策略，通常最优。
    但若单位价值相同，则需结合次级规则（如优先选重量小的物品）来避免歧义。

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
# 背包问题的贪心算法实现（分数背包）

# 物品信息：重量和价值
items = [
    {"name": "A", "weight": 35, "value": 10},
    {"name": "B", "weight": 30, "value": 40},
    {"name": "C", "weight": 60, "value": 30},
    {"name": "D", "weight": 50, "value": 50},
    {"name": "E", "weight": 40, "value": 35},
    {"name": "F", "weight": 10, "value": 40},
    {"name": "G", "weight": 25, "value": 30},
]

capacity = 150  # 背包容量

# 计算单位价值（价值/重量）
for item in items:
    item["unit_value"] = item["value"] / item["weight"]

# 按单位价值从高到低排序
items.sort(key=lambda x: x["unit_value"], reverse=True)

total_value = 0  # 总价值
total_weight = 0  # 总重量
selected_items = []  # 记录装入背包的物品及其比例

for item in items:
    if total_weight + item["weight"] <= capacity:
        # 能全部装入
        total_weight += item["weight"]
        total_value += item["value"]
        selected_items.append((item["name"], 1))  # 1表示全部装入
    else:
        # 装入剩余容量的部分
        remain = capacity - total_weight
        fraction = remain / item["weight"]
        total_weight += remain
        total_value += item["value"] * fraction
        selected_items.append((item["name"], fraction))
        break  # 背包满了，停止装入

# 输出结果
print(f"背包总重量: {total_weight:.2f}")
print(f"背包总价值: {total_value:.2f}")
print("装入背包的物品及比例:")
for name, frac in selected_items:
    if frac == 1:
        print(f"  {name} - 全部装入")
    else:
        print(f"  {name} - 装入 {frac:.2%}")

分发糖果（Leetcode 题目）

题目：

老师想给站成一排的 N 个孩子分发糖果，分配规则如下：

  • 每个孩子至少分配到 1 个糖果；
  • 相邻的孩子中，评分更高的孩子必须获得更多的糖果。

那么，老师至少需要准备多少颗糖果呢？

题目示例

  • 示例 1：

    输入：[1,0,2]
    输出：5
    解释：可以分配糖果为 [2,1,2]。

  • 示例 2：

    输入：[1,2,2]
    输出：4
    解释：可以分配糖果为 [1,2,1]，第三个孩子得到 1 颗糖果，满足条件。

规则分析

设相邻的两个孩子为 A 和 B，A 在 B 左边，则：

  • 左规则：当 ratings[B] > ratings[A] 时，B 得到的糖果数比 A 多；
  • 右规则：当 ratings[A] > ratings[B] 时，A 得到的糖果数比 B 多。

要满足所有相邻孩子都符合这两个规则，意味着每个孩子的糖果数既满足左规则又满足右规则。

算法思路

  1. 初始化：先给每个孩子 1 颗糖果。

  2. 从左到右遍历，根据左规则更新糖果数：

    • 若当前孩子评分比左边孩子高，则当前孩子的糖果数为左边孩子糖果数 + 1；
    • 否则保持不变。

  3. 从右到左遍历，根据右规则更新糖果数：

    • 若当前孩子评分比右边孩子高，且糖果数不够，则更新为右边孩子糖果数 + 1。

  4. 最后，所有孩子糖果数取两次遍历后的最大值即满足左右规则，计算总和即为所需糖果总数。

代码实现（C++）

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
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if (n == 0) return 0;

        // 每个孩子至少分配1颗糖果
        vector<int> candies(n, 1);

        // 左规则遍历：从左到右
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 右规则遍历：从右到左
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                candies[i] = candies[i + 1] + 1;
            }
        }

        // 计算糖果总数
        int total = 0;
        for (int c : candies) {
            total += c;
        }

        return total;
    }
};