软考-软件设计师：算法策略：贪心法（一般用于求满意解） 作者：马育民 • 2026-02-11 20:24 • 阅读：10000 # 介绍 **局部最优，但整体不见得最优**。每步有明确的、既定的策略。 ### 审题技巧 没有明确的文字特征，可能有 **关注现在** 字样，如果做题时，遇到这种情况，一般是贪心法 ### 经典问题 - 背包问题页（如装箱） - 多机调度 - 找零钱问题 - **最小生成树问题(普里姆算法、克鲁斯卡尔算法)** # 案例 - 部分背包问题 [](https://www.malaoshi.top/upload/0/0/1GWwxPgS6OL.png) 如上图： 有一个背包，背包容量是 `70` 有 `3` 个物品： - 物品1，重量 `20`，价值 `140` - 物品2，重量 `30`，价值 `180` - 物品3，重量 `40`，价值 `200` 物品可以 **分割成任意大小**。要求尽可能让装入背包中的物品 **总价值最大**，但不能超过总容量。 **实现方式一（局部最优、整体不是最优）：** 计算出各个物品的单价，即：`单价 = 价格 / 重量`，将 **单价 最高** 的物品装起来，此时 **局部最优** - 物品1，单价 `7` - 物品2，单价 `6` - 物品3，单价 `5` `物品1`、`物品2` **单价 最高**，且总重量不超过背包限制，将其装入到背包，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwxRXEYWD.png) **缺点：** - 局部最优：放入的物品都是单价最高的 - 整体不是最优：如果放入 `物品2`、`物品3`，总价值是 `380`，超过本方法的价值 **实现方式二（局部最优、整体不是最优）：** 将 **价值 最高的物品** 装起来，此时 **局部最优** - 物品1，重量 `20`，价值 `140` - 物品2，重量 `30`，价值 `180` - 物品3，重量 `40`，价值 `200` `物品2`、`物品3` 价值最高，且总重量不超过背包限制，将其装入到背包，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwxWT7wgT.png) **缺点：** - 局部最优：放入的物品价值最高 - 整体不是最优：见实现方法三 **实现方式三（最优）：** 计算出各个物品的单价，即：`单价 = 价格 / 重量`，将 **单价 最高** 的物品装起来，此时 **局部最优** - 物品1，单价 `7` - 物品2，单价 `6` - 物品3，单价 `5` `物品1`、`物品2` **单价 最高**，且总重量不超过背包限制，将其装入到背包，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwxRXEYWD.png) 还空出 `20` 的容量，将 `物品3` 分割一半，放入进去，如下： [](https://www.malaoshi.top/upload/0/0/1GWwxbUYuhd.png) **此时才是最优解** # 案例 - 旅行家问题 有4个点：A起点，B、C、D，各点距离如下： - A→B = **1**（最近，贪心必选） - A→C = **2** - A→D = **100** - B→C = **100**（巨远） - B→D = **100**（巨远） - C→D = **1**（超级近） 旅行家 **每个城市只走一次，最后回到起点 A**，走的路程最短 用贪心算法是错误的 ### 贪心算法（最近邻） 1. A 出发，最近是 B（1） 路径：A→B 2. 在 B，只能去 C 或 D，都 100，选 C 路径：A→B→C 3. 在 C，只剩 D 路径：A→B→C→D 4. D 返回 A（100） 总距离 = 1 + 100 + 1 + 100 = **202** ##### 时间复杂度 这个贪心算法的核心流程是： 1. 从中央仓库出发，作为当前地点。 2. 从所有未访问的运输目的地中，找到离当前地点最近的一个，将其加入路径，并标记为已访问。 3. 将新加入的地点设为当前地点。 4. 重复步骤2和3，直到所有运输目的地都被访问过。 5. 最后从最后一个地点返回中央仓库。 对于 `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 原文出处：http://malaoshi.top/show_1GW2lAoteCya.html