专题进阶 · 搜索与回溯推荐总顺序 · 第 77 / 148 课

先构造单调可行性判定,再在答案区间找到最小可行值。

先学会这些,再进入本课 二分查找 贪心思想
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 搜索与回溯

二分答案Binary Search on Answer

把求最优值转成可行性判定;只有可行性对答案单调时才能二分。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

先构造单调可行性判定,再在答案区间找到最小可行值。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

包裹重量 [3,2,2,4,1,4] 必须按原顺序在 3 天内运完,求最小船容量。

02一步步得到方法

把最优值改成是非题

给定容量 C,按顺序装包裹,放不下才开启下一天,检查天数是否≤D。若 C 可行,更大的容量也可行,因为至少可以照搬原分组。因此答案轴上是若干 False 后接若干 True。

最小容量至少为最重包裹,最多为总重量。这里二分的是容量,不是包裹数组下标;包裹顺序不能为了方便而重排。

判定器自身也要证明

在固定 C 下,每天尽量装到不能再装。若某方案第一天比贪心装得少,后面不会因此少运任何包裹;把贪心多装的前缀提前,不会增加剩余天数。逐日交换可说明贪心使用最少天数。

二分维护答案在闭区间 [lo,hi] 中。mid 可行则 hi=mid,保留这个候选;不可行则 lo=mid+1。若写成 hi=mid−1 但没有额外记录答案,就可能丢掉最小可行值。

先写出判定的单调方向

先不要写二分循环,而是定义 check(x) 的含义,并证明从某个位置开始真假只改变一次。比如容量越大越能完成运输,是 false→true;你寻找的是第一个 true,而非任意可行值。

每轮保持答案位于当前边界约定内,判定可行时收紧右边界,不可行时跳过 mid。判定成本可能是 O(n),所以整体常为 O(n log R),不能只写二分的 O(log R)。

03把一个小例子完全算清楚

重量 [3,2,2,4,1,4],D=3,初始容量区间 [4,16]。

步骤计算与状态为什么这样做
C=10[3,2,2]、[4,1,4],2 天可行,上界降到 10
C=7[3,2,2]、[4,1]、[4],3 天可行
C=5[3,2]、[2]、[4,1]、[4],4 天不可行
C=6[3,2]、[2,4]、[1,4],3 天答案 6

窄屏可左右滑动表格,阅读完整计算与理由。

容量可行性具有方向一致的单调性,才允许排除一整段答案。

04为什么这个方法成立

  1. 判定器给出固定容量下最少的分组天数。
  2. 可行容量向上封闭,最小可行值不会被更新排除。
  3. 每次严格缩短整数区间,lo=hi 时即为最小可行容量。

05把推导翻译成代码

Python · 可独立运行的教学实现

def minimum_capacity(weights, days):
    if not weights or days < 1 or any(w <= 0 for w in weights):
        raise ValueError("positive weights and days required")
    def feasible(capacity):
        used, load = 1, 0
        for w in weights:
            if load + w > capacity:
                used += 1
                load = 0
            load += w
        return used <= days
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

逐个理解关键决定

hi = mid
mid 本身可能正是答案,必须保留。
load + w > capacity
刚好等于容量仍能装,不应提前开新一天。

06时间、空间与实现范围

每次判定 O(n),容量整数区间宽 W,总 O(n log(W+1)),辅助空间 O(1)。

不是所有优化问题都具有单调判定,必须先证明 True/False 结构。

07改变条件,检查哪里会出错

判定是否恰好用 D 天

恰好天数不一定保持需要的单调结构;使用至多 D 天,并依据题意说明是否可拆分天数。

上下界不包含可行解

应根据题目构造保证可行的上界,并说明是否可能无解,否则循环结束的数字未必有意义。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

D=1 时答案多少?

需要一点提示

所有包裹同一天。

查看解析与答案

sum(weights)=16。

练习 2 · 边界与辨析

D=6 时答案多少?

需要一点提示

每天至少可运一个。

查看解析与答案

max(weights)=4。

练习 3 · 变式与迁移

如果允许任意重排,当前判定仍解决原任务吗?

需要一点提示

顺序是否改变了可行方案集合?

查看解析与答案

不是同一个问题;贪心证明基于连续前缀分组,任意装箱需要重新建模。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。