介绍
局部最优，但整体不见得最优。每步有明确的、既定的策略。
审题技巧
没有明确的文字特征，可能有 关注现在 字样，如果做题时，遇到这种情况，一般是贪心法
经典问题
- 背包问题页（如装箱）
- 多机调度
- 找零钱问题
- 最小生成树问题(普里姆算法、克鲁斯卡尔算法)
案例 - 部分背包问题
如上图：
有一个背包，背包容量是 70
有 3 个物品：
- 物品1，重量
20，价值140 - 物品2，重量
30，价值180 - 物品3，重量
40，价值200
物品可以 分割成任意大小。要求尽可能让装入背包中的物品 总价值最大，但不能超过总容量。
实现方式一（局部最优、整体不是最优）：
计算出各个物品的单价，即：单价 = 价格 / 重量，将 单价 最高 的物品装起来，此时 局部最优
- 物品1，单价
7 - 物品2，单价
6 - 物品3，单价
5
物品1、物品2 单价 最高，且总重量不超过背包限制，将其装入到背包，如下图：
缺点：
- 局部最优：放入的物品都是单价最高的
- 整体不是最优：如果放入
物品2、物品3，总价值是380，超过本方法的价值
实现方式二（局部最优、整体不是最优）：
将 价值 最高的物品 装起来，此时 局部最优
- 物品1，重量
20，价值140 - 物品2，重量
30，价值180 - 物品3，重量
40，价值200
物品2、物品3 价值最高，且总重量不超过背包限制，将其装入到背包，如下图：
缺点：
- 局部最优：放入的物品价值最高
- 整体不是最优：见实现方法三
实现方式三（最优）：
计算出各个物品的单价，即：单价 = 价格 / 重量，将 单价 最高 的物品装起来，此时 局部最优
- 物品1，单价
7 - 物品2，单价
6 - 物品3，单价
5
物品1、物品2 单价 最高，且总重量不超过背包限制，将其装入到背包，如下图：
还空出 20 的容量，将 物品3 分割一半，放入进去，如下：
此时才是最优解
案例 - 旅行家问题
有4个点：A起点，B、C、D，各点距离如下：
- A→B = 1（最近，贪心必选）
- A→C = 2
A→D = 100
B→C = 100（巨远）
- B→D = 100（巨远）
- C→D = 1（超级近）
旅行家 每个城市只走一次，最后回到起点 A，走的路程最短
用贪心算法是错误的
贪心算法（最近邻）
- A 出发，最近是 B（1）
路径：A→B - 在 B，只能去 C 或 D，都 100，选 C
路径：A→B→C - 在 C，只剩 D
路径：A→B→C→D - D 返回 A（100）
总距离 = 1 + 100 + 1 + 100 = 202
时间复杂度
这个贪心算法的核心流程是：
- 从中央仓库出发，作为当前地点。
- 从所有未访问的运输目的地中，找到离当前地点最近的一个，将其加入路径，并标记为已访问。
- 将新加入的地点设为当前地点。
- 重复步骤2和3，直到所有运输目的地都被访问过。
- 最后从最后一个地点返回中央仓库。
对于 n 个运输目的地，我们需要执行 n 次“选择下一个地点”的操作。
单次选择的时间复杂度
在每一次选择下一个地点时，我们需要：
- 遍历所有未访问的运输目的地。
- 计算（或查找）当前地点到每个未访问地点的距离。
- 找到其中距离最小的那个。
在最坏情况下，第一次选择时有 n 个地点可选，第二次有 n-1 个，第三次有 n-2 个，以此类推。因此，单次选择的时间复杂度是线性的，即 O(k)，其中 k 是当前未访问地点的数量。
总时间复杂度计算
n + (n-1) + (n-2) + \ldots + 1 = \frac{n(n+1)}{2} = n^2
真正最优路径（不贪心）
最优走法：
A → C → D → B → A
总距离 = 2 + 1 + 100 + 1 = 104
- 贪心：202
- 最优：104