模块 08: 算法设计

把问题分为小实例，求解后合并。归并排序平衡划分满足 T(n)=2T(n/2)+Θ(n)，每层线性、层数对数。二分仅解一半，为 T(n)=T(n/2)+Θ(1)。子问题数量与合并成本都重要，仅称递归不能确定增长。

贪心立即选择局部有利项。最多不重叠区间可选最早结束，再处理兼容区间。最优方案首区间可换成最早结束者，不推迟其他开始，数量不变，剩余仍同类问题。最早开始缺少此论证，早长区间可阻挡许多短区间。最大总价值是不同问题，通常不能用此规则。

回溯扩展部分解，拒绝不可能分支，并撤销选择再试替代。n 项子集共 2^n 种，剪枝可能减少实际探索但最坏仍指数。小实例穷举可作为快速算法对照。剪枝需论证，不能因局部不够好就排除最优可能。

动态规划复用重叠子问题。best[v] 表示金额 v 最少硬币数，基础零，不可达为无穷。对正硬币 c≤v，取 best[v−c]+1 最小值。按 v 递增让依赖就绪。k 种硬币、目标 A 的时间 O(kA)、空间 O(A)，对数值 A 伪多项式，并非对 A 位长多项式。六元用 [1,3,4] 时贪心给 4+1+1，输给 3+3。

只有最优值不一定告诉用户如何操作。每次改善状态保存选择的前驱，再逆向恢复。独立检查可行性：硬币总值等于目标，区间不重叠。小案例与穷举对照最优性，可区分实现错误与递推错误。零金额的空解有效，不可达正金额则无解。

下载脚本，在终端中使用 Python 3.11 或更新版本运行：python m08_greedy.py. Windows 也可使用 py -3；部分系统使用 python3。实验仅用标准库。先预测结果，再运行并完成变体。不要使用 -O，以保留断言。下方输出由构建器实际运行捕获，两种语言使用相同代码与输出。

最大化兼容半开区间数量，端点可相接，穷举检查小实例。

下载 m08_greedy.py

"""Earliest-finish interval scheduling, checked against exhaustive search."""
from itertools import combinations
def compatible(intervals):
    ordered = sorted(intervals)
    return all(a[1] <= b[0] for a, b in zip(ordered, ordered[1:]))
def schedule(intervals):
    result, end = [], float("-inf")
    for start, finish in sorted(intervals, key=lambda item: item[1]):
        if start >= finish:
            raise ValueError("nonempty intervals required")
        if start >= end:
            result.append((start, finish)); end = finish
    return result

jobs = [(0, 4), (1, 2), (2, 3), (3, 5), (4, 6)]
chosen = schedule(jobs)
optimal = max(len(subset) for size in range(len(jobs)+1) for subset in combinations(jobs, size) if compatible(subset))
print("chosen:", chosen, "optimal count:", optimal)
assert len(chosen) == optimal == 3
assert schedule([]) == []

chosen: [(1, 2), (2, 3), (3, 5)] optimal count: 3

1. 改用最早开始，构造失败。
2. 加零时长任务，解释拒绝。
3. 为任务加价值，说明对照应如何改变。

检查六元的各状态并恢复硬币，无穷标记不可达。

下载 m08_dynamic.py

"""Minimum coin count with reconstruction; impossible values return None."""
def min_coins(coins, amount):
    if amount < 0 or any(c <= 0 for c in coins):
        raise ValueError("nonnegative amount and positive coins required")
    best, previous = [0] + [float("inf")] * amount, [None] * (amount + 1)
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and best[value - coin] + 1 < best[value]:
                best[value] = best[value - coin] + 1; previous[value] = coin
    if best[amount] == float("inf"):
        return None
    selected = []
    while amount:
        coin = previous[amount]
        selected.append(coin); amount -= coin
    return selected

for coins, amount in [([1, 3, 4], 6), ([2, 4], 3), ([1, 3, 4], 0)]:
    result = min_coins(coins, amount)
    print(coins, amount, "->", result)
    if result is not None: assert sum(result) == amount
assert min_coins([1, 3, 4], 6) == [3, 3]
assert min_coins([2, 4], 3) is None

[1, 3, 4] 6 -> [3, 3]
[2, 4] 3 -> None
[1, 3, 4] 0 -> []

1. 测试 [2,5] 的一与七。
2. 比较贪心与动态规划。
3. 加入只返回数量的版本，比较存储职责。

先尝试，再展开解答。★ 应用概念；★★ 结合概念；★★★ 进行设计或证明。

选择答案查看反馈，重置后可重做。无需 JavaScript 也可阅读答案表。

• MIT 算法资料 — 阅读动态规划，在例子中指出状态、基础与转移。

对新优化任务先定义目标、可行解与状态，再选策略。模块 09 将研究执行这些过程的机器。