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为什么这个方法成立
- 判定器给出固定容量下最少的分组天数。
- 可行容量向上封闭,最小可行值不会被更新排除。
- 每次严格缩短整数区间,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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
D=1 时答案多少?
需要一点提示
所有包裹同一天。
查看解析与答案
sum(weights)=16。
D=6 时答案多少?
需要一点提示
每天至少可运一个。
查看解析与答案
max(weights)=4。
如果允许任意重排,当前判定仍解决原任务吗?
需要一点提示
顺序是否改变了可行方案集合?
查看解析与答案
不是同一个问题;贪心证明基于连续前缀分组,任意装箱需要重新建模。