1. 贪心算法（Greedy）
1.1 核心思想
每一步都做出在当前看来最优的选择，希望最终结果也是全局最优。
两个关键性质：
- 贪心选择性质：局部最优能导向全局最优
- 最优子结构性质：问题的最优解包含子问题的最优解
1.2 经典问题：活动选择
def activity_selection(activities):
"""
给定活动开始和结束时间，选择最多不冲突的活动
贪心策略：每次选结束时间最早的活动
"""
# 按结束时间排序
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
last_end = activities[0][1]
for i in range(1, len(activities)):
if activities[i][0] >= last_end: # 开始时间 ≥ 上一个结束时间
selected.append(activities[i])
last_end = activities[i][1]
return selected
# 示例：活动 = [(开始, 结束), ...]
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10)]
print(activity_selection(activities))
1.3 经典问题：分数背包
def fractional_knapsack(weights, values, capacity):
"""
物品可以分割，贪心策略：按单位价值从高到低选取
注意：此策略对 0-1 背包不成立！
"""
items = [(values[i] / weights[i], weights[i], values[i])
for i in range(len(weights))]
items.sort(reverse=True) # 按单位价值降序
total_value = 0.0
for ratio, w, v in items:
if capacity >= w:
total_value += v
capacity -= w
else:
total_value += capacity * ratio
break
return total_value
1.4 经典问题：最小生成树（Prim/Kruskal）
# 见前文图算法中的 Prim 和 Kruskal 实现
# 它们都是基于贪心策略：
# - Prim：每次选连接已选集合和未选集合的最短边
# - Kruskal：每次选全局最短且不形成环的边
1.5 经典问题：哈夫曼编码
import heapq
def huffman_coding(freq):
"""
贪心策略：每次合并频率最小的两棵树
用于数据压缩（如 ZIP）
"""
heap = [[w, [s, ""]] for s, w in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
# 左路标 0，右路标 1
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
# 示例
freq = {'a': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5}
codes = huffman_coding(freq)
for char, code in codes:
print(f"{char}: {code}")
2. 回溯法（Backtracking）
2.1 核心框架
回溯 = DFS + 剪枝
通用模板：
function backtrack(路径, 选择列表):
if 满足结束条件:
添加结果
return
for 选择 in 选择列表:
做选择
backtrack(路径, 新选择列表)
撤销选择（恢复现场）
2.2 全排列
def permute(nums):
"""所有不重复排列"""
n = len(nums)
result = []
def backtrack(path, used):
if len(path) == n:
result.append(path[:])
return
for i in range(n):
if used[i]:
continue
# if i > 0 and nums[i] == nums[i-1] and not used[i-1]: # 去重
# continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * n)
return result
2.3 N 皇后问题
def solve_n_queens(n):
"""
每行放一个皇后，列和对角线不能冲突
"""
result = []
board = [['.'] * n for _ in range(n)]
def is_valid(row, col):
# 检查列
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上对角线
for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if board[i][j] == 'Q':
return False
# 检查右上对角线
for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
if board[i][j] == 'Q':
return False
return True
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if not is_valid(row, col):
continue
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
backtrack(0)
return result
2.4 子集求和
def subset_sum(nums, target):
"""
找出所有和为 target 的子集（元素不重复使用）
"""
nums.sort()
result = []
def backtrack(start, path, curr_sum):
if curr_sum == target:
result.append(path[:])
return
if curr_sum > target:
return # 剪枝：和已超过目标
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # 去重
if curr_sum + nums[i] > target:
break # 剪枝：后续元素更大
path.append(nums[i])
backtrack(i + 1, path, curr_sum + nums[i])
path.pop()
backtrack(0, [], 0)
return result
3. 剪枝策略
3.1 常用剪枝技巧
| 剪枝类型 | 说明 | 示例 |
|---|---|---|
| 和/积超界 | 当前状态不可能达到目标 | 子集和超出 target |
| 重复状态 | 相同状态不再重复搜索 | 排序后跳过相同元素 |
| 对称性 | 利用对称减少搜索 | 图染色只考虑不同排列 |
| 下界估计 | 估计剩余最小值，仍不够则剪 | 分支限界 |
3.2 分支限界（Branch and Bound）
import heapq
def branch_bound_knapsack(weights, values, capacity):
"""
0-1 背包的分支限界解法
用优先队列（最大堆）按上界排序
"""
n = len(weights)
items = sorted(range(n), key=lambda i: values[i] / weights[i], reverse=True)
# 计算上界：当前价值 + 贪心填充剩余容量
def bound(idx, curr_w, curr_v):
if curr_w >= capacity:
return 0
remaining = capacity - curr_w
upper = curr_v
for i in range(idx, n):
j = items[i]
if weights[j] <= remaining:
upper += values[j]
remaining -= weights[j]
else:
upper += remaining * values[j] / weights[j]
break
return upper
max_value = 0
# (-上界, 当前索引, 当前重量, 当前价值)
pq = [(-bound(0, 0, 0), 0, 0, 0)]
while pq:
neg_bound, idx, curr_w, curr_v = heapq.heappop(pq)
if idx == n:
max_value = max(max_value, curr_v)
continue
# 不选当前物品
b = bound(idx + 1, curr_w, curr_v)
if b > max_value:
heapq.heappush(pq, (-b, idx + 1, curr_w, curr_v))
# 选当前物品
j = items[idx]
if curr_w + weights[j] <= capacity:
new_v = curr_v + values[j]
b = bound(idx + 1, curr_w + weights[j], new_v)
if b > max_value:
heapq.heappush(pq, (-b, idx + 1, curr_w + weights[j], new_v))
return max_value
4. 贪心 vs 回溯决策树
贪心：
当前选择 → 子问题 → 最优解（不回头）
↓
可能不是全局最优（需证明）
回溯：
当前选择 → 子问题 → 所有可能解
↓
剪枝排除不可能分支
↓
找到最优或所有解（穷举搜索）
5. 总结
| 算法 | 时间复杂度 | 空间复杂度 | 是否保证最优 |
|---|---|---|---|
| 贪心 | O(n log n) ~ O(n) | O(1) ~ O(n) | 不一定 |
| 回溯 | 指数级（O(2ⁿ) 或 O(n!)） | O(n) 递归栈 | ✅（搜索全部解空间） |
| 分支限界 | 最坏指数级，实际剪枝后好很多 | O(待展开节点数) | ✅ |
实战建议：先尝试贪心（因为快），如果不能证明最优性，再用回溯/动态规划。
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。