目录
一、贪心算法 (Greedy Algorithm)
核心思想
图形化示例：找零钱问题
本题中的贪心应用
贪心算法特点
二、回溯算法 (Backtracking Algorithm)
核心思想
图形化示例：从 [0, 1, 4] 中选2个的所有组合
详细的回溯树（选2个处理器）
回溯算法代码执行流程
执行过程可视化
回溯算法特点
三、两种算法的对比
决策树对比图
实际应用场景对比表
四、本题中的综合应用
一、贪心算法 (Greedy Algorithm)
核心思想
每一步都做出当前看起来最优的选择，期望通过局部最优达到全局最优。
图形化示例：找零钱问题
假设你需要找零36元，有面值为[20, 10, 5, 1]的纸币，如何用最少的纸币数量？
目标：36元 可用纸币：[20, 10, 5, 1] 贪心策略：每次选择不超过剩余金额的最大面值 步骤图示： ┌─────────────────────────────────────┐ │ 剩余: 36元 │ │ ↓ 选择最大: 20元 │ │ 剩余: 16元 │ │ ↓ 选择最大: 10元 │ │ 剩余: 6元 │ │ ↓ 选择最大: 5元 │ │ 剩余: 1元 │ │ ↓ 选择最大: 1元 │ │ 剩余: 0元 ✓ │ └─────────────────────────────────────┘ 结果：[20, 10, 5, 1] = 4张纸币本题中的贪心应用
申请1个处理器，可用处理器：[0, 1, 4, 5, 6, 7] 链路分组： ┌──────────────┐ ┌──────────────┐ │ 链路A (0-3) │ │ 链路B (4-7) │ │ 可用: [0,1] │ │ 可用: [4,5,6,7] │ │ 数量: 2 │ │ 数量: 4 │ └──────────────┘ └──────────────┘ 优先级顺序：[1, 3, 2, 4] ↓ 检查优先级1: 链路A(2个)❌ 链路B(4个)❌ ↓ 检查优先级3: 链路A(2个)❌ 链路B(4个)❌ ↓ 检查优先级2: 链路A(2个)✓ 链路B(4个)❌ ↓ 找到匹配！选择链路A，停止搜索贪心算法特点
✅优点：
- 简单高效
- 时间复杂度低
- 代码实现简洁
❌缺点：
- 不一定能得到全局最优解
- 需要问题满足"贪心选择性质"
二、回溯算法 (Backtracking Algorithm)
核心思想
通过试探性地构建解决方案，遇到不满足条件时就回退（撤销选择），继续尝试其他路径。
图形化示例：从 [0, 1, 4] 中选2个的所有组合
开始 [] | ┌─────────────┼─────────────┐ | | | 选0 选1 选4 | | | [0] [1] [4] | | | ┌───┴───┐ ┌───┴───┐ | | | | | | 选1 选4 选4 (无) (无) | | | [0,1]✓ [0,4]✓ [1,4]✓ 回溯过程： 1. 选择0 → 选择1 → [0,1]完成 ✓ → 回退到0 2. 从0 → 选择4 → [0,4]完成 ✓ → 回退到根 3. 选择1 → 选择4 → [1,4]完成 ✓ → 回退到根 4. 选择4 → 无法再选 → 结束 最终结果：[[0,1], [0,4], [1,4]]详细的回溯树（选2个处理器）
[] start=0 | ┌───────────────┼───────────────┐ ↓ ↓ ↓ [0] [1] [4] start=1 start=2 start=3 | | | ┌───┴───┐ ┌───┴───┐ X (无后续) ↓ ↓ ↓ ↓ [0,1] [0,4] [1,4] X ✓ ✓ ✓ 图例说明： ↓ : 向下探索（选择元素） ✓ : 找到一个有效组合 X : 无法继续（已到数组末尾或长度已满） 回退: 撤销最后一次选择，尝试下一个选项回溯算法代码执行流程
function getCombinations(arr, k) { const result = []; function backtrack(start, current) { // 递归终止条件 if (current.length === k) { result.push([...current]); return; } // 从start开始遍历 for (let i = start; i < arr.length; i++) { current.push(arr[i]); // ① 做选择 backtrack(i + 1, current); // ② 递归探索 current.pop(); // ③ 撤销选择（回溯） } } backtrack(0, []); return result; }执行过程可视化
输入: arr=[0,1,4], k=2 调用栈变化： ┌─────────────────────────────────────────┐ │ backtrack(0, []) │ │ i=0: current=[0] │ │ ├─ backtrack(1, [0]) │ │ │ i=1: current=[0,1] → 保存✓ │ │ │ 回退: current=[0] │ │ │ i=2: current=[0,4] → 保存✓ │ │ │ 回退: current=[0] │ │ 回退: current=[] │ │ i=1: current=[1] │ │ ├─ backtrack(2, [1]) │ │ │ i=2: current=[1,4] → 保存✓ │ │ │ 回退: current=[1] │ │ 回退: current=[] │ │ i=2: current=[4] │ │ ├─ backtrack(3, [4]) │ │ │ (i=3 >= arr.length, 循环结束) │ │ 回退: current=[] │ └─────────────────────────────────────────┘ 结果: [[0,1], [0,4], [1,4]]回溯算法特点
✅优点：
- 能找到所有可能的解
- 适合求解组合、排列、子集等问题
- 通过剪枝可以优化性能
❌缺点：
- 时间复杂度较高（指数级）
- 需要额外的栈空间
三、两种算法的对比
决策树对比图
贪心算法（只走一条路）： 根节点 ↓ 选最优选项 ↓ 选最优选项 ↓ 结束 ✓ 特点：一条路走到底，不回头 回溯算法（探索所有路径）： 根节点 / | \ 路径1 路径2 路径3 / \ / \ / \ ✓ ✓ ✓ X X ✓ 特点：尝试所有可能，遇到死路就回退实际应用场景对比表
| 特性 | 贪心算法 | 回溯算法 |
|---|---|---|
| 决策方式 | 局部最优 | 全局搜索 |
| 是否回退 | 否 | 是 |
| 解的数量 | 1个 | 所有可能 |
| 时间复杂度 | O(n) ~ O(n log n) | O(2^n) ~ O(n!) |
| 典型应用 | 霍夫曼编码、最小生成树、活动选择 | N皇后、数独、组合总和 |
四、本题中的综合应用
完整流程图： 输入: [0,1,4,5,6,7], num=1 第一步：分组 ┌──────────────┐ ┌──────────────┐ │ 链路A: [0,1] │ │ 链路B: [4,5,6,7] │ └──────────────┘ └──────────────┘ 第二步：贪心选择最优链路 优先级: [1, 3, 2, 4] ↓ 检查长度2: 链路A匹配 ✓ 第三步：回溯生成组合 从[0,1]中选1个： [] / \ [0] [1] ✓ ✓ 输出: [[0], [1]]
