1
2

路径 A：… → Agent 1（代价 5）     进度 j
路径 B：… → Agent 2（代价 5）     进度 j

1
2
3
4
5

① 状态定义：f[...] 的语义是什么？（一句话说清，且要含"恰好/不超过"的口径）
② 转移方程：f[当前] 由哪些 f[子] 推来？每项的物理含义是什么？
③ 初始化：最小的子问题取什么值？（决定边界是否正确）
④ 遍历顺序：按什么顺序填表？（决定每个 f[子] 读到的是旧值还是新值）
⑤ 答案位置：最终答案是哪个 f 值？（多输出题往往要事后扫描还原）

1
2
3
4
5
6
7
8
9

二维版本：
① f[i][c] = 只考虑前 i 件、容量不超过 c 时的最大价值
② f[i][c] = max( f[i−1][c], f[i−1][c − w_i] + v_i )   仅当 c ≥ w_i
③ f[0][c] = 0；f[i][0] = 0
④ i 从小到大；c 方向任意（读的是上一层 i−1，与 c 无关）
⑤ f[n][C]

一维滚动版本（省掉 i 那一维）：f[c] = max(f[c], f[c − w_i] + v_i)，仅当 c ≥ w_i
④ c 必须从大到小（倒序）遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

为什么必须倒序——本章第一个必须讲透的机理：
设 C = 5，物品 w = 2、v = 10，f 初值全 0。
【正序 c = 0,1,2,3,4,5】
  c=2：f[2] = max(f[2], f[0]+10) = 10
  c=4：f[4] = max(f[4], f[2]+10) = 20    ← f[2] 已被本轮更新过
  ⟹ f[5] = 20 ⟹ 同一件物品被选了两次 ⟹ 这其实是完全背包的语义
【倒序 c = 5,4,3,2,1,0】
  c=4：f[4] = max(f[4], f[2]+10)，此刻 f[2] 还是旧值 0 ⟹ f[4] = 10
  c=2：f[2] = max(f[2], f[0]+10) = 10
  ⟹ f[5] = 10 ⟹ 每件物品至多用一次 ⟹ 正确的 0/1 语义

1
2
3
4
5
6
7
8

def knapsack01(weights, values, cap):
    # f[c] 口径是"容量不超过 c"，初值全 0 天然合法（什么都不选也是合法方案）
    f = [0] * (cap + 1)
    for w, v in zip(weights, values):
        # 倒序：保证 f[c-w] 读到的还是"没考虑当前物品"的旧值，即每件至多选一次
        for c in range(cap, w - 1, -1):
            f[c] = max(f[c], f[c - w] + v)
    return f[cap]

1
2
3
4
5
6
7
8
9

def knapsack_complete(weights, values, cap):
    # 完全背包：每件可选任意多次；f[c] 是"容量不超过 c"的最大价值
    f = [0] * (cap + 1)
    for w, v in zip(weights, values):
        # 正序：f[c-w] 在本轮已被更新为"考虑过当前物品"的值，
        # 于是同一物品可以继续叠加，恰好对应"可重复选取"
        for c in range(w, cap + 1):
            f[c] = max(f[c], f[c - w] + v)
    return f[cap]

1
2
3
4
5
6
7
8
9

① 状态：进度"达到或超过 100"即完成，真正有用的进度只有 0..99；
        又因"不能连续两次同一 Agent"，必须记住上一次是谁：
          f[j]    = 进度恰为 j 时的最小总代价
          last[j] = 取到 f[j] 时最后调用的 Agent
          s[j]    = 排除 last[j] 后、进度为 j 的最小总代价（次小值）
② 转移：j → j + p_k 时，base = s[j] if k == last[j] else f[j]
③ 初始化：f[0] = s[0] = 0，last[0] = −1；把起点写成"对每个 k 都取 min"，第一次调用不受限这条特例就并进了通用转移
④ 遍历顺序：p_i ≥ 1 保证进度严格递增，按 j 从小到大单向递推即可
⑤ 答案：所有 t = j + p_k ≥ 100 的候选中的最小值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

情形 1：k == last[j]
  被排除的正是最小值的持有者
  ⟹ 剩下的候选恰好是"除 last[j] 之外的全部"
  ⟹ 它们的最小值按 s[j] 的定义就是 s[j]

情形 2：k != last[j]
  f[j] 的持有者不是 k，所以 f[j] 没有被排除
  ⟹ 它是"排除 k 之后"这个候选集合的成员
  ⟹ 而该集合是原集合的子集，其最小值不可能小于全层最小值 f[j]
  ⟹ 同时 f[j] 在集合内 ⟹ "排除 k 之后的最小值" = f[j]
  两情形穷尽，命题成立。∎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

INF = float('inf')

def min_total_cost(n, p, c):
    """完全背包 + 相邻不同约束：f/s/last 三层信息把 O(100·N²) 降到 O(100·N)"""
    f, s, last = [INF] * 100, [INF] * 100, [-1] * 100
    f[0], s[0], ans = 0, 0, INF   # 虚拟起点：第一次调用不受"相邻不同"限制
    for j in range(100):      # p_i >= 1 ⟹ 进度严格递增 ⟹ 升序即拓扑序
        if f[j] == INF: continue
        for k in range(n):
            base = s[j] if k == last[j] else f[j]   # 撞上持有者就退而用次小值
            if base == INF: continue
            cost, t = base + c[k], j + p[k]
            if t >= 100:                           # 到达目标即结束，不入表
                ans = min(ans, cost); continue
            if cost < f[t]:
                if last[t] == k: f[t] = cost                    # 规则 1：同一 Agent 变便宜，s[t] 不动
                else: s[t], f[t], last[t] = f[t], cost, k        # 规则 2：老的最小让位成次小
            elif last[t] != k and cost < s[t]: s[t] = cost       # 规则 3：刷新次小值
            # 规则 4：last[t] == k 且未便宜过 ⟹ 落在两个分支之外，丢弃
    return -1 if ans == INF else ans

1
2
3
4

for x, y, w in tasks:
    for a in range(cap_a, x - 1, -1):        # 两维都倒序
        for b in range(cap_b, y - 1, -1):
            f[a][b] = max(f[a][b], f[a - x][b - y] + w)

1
2
3
4
5
6

上界方向：f[a* − 1][B] < best
  a* 是"使 f[·][B] 达到 best 的最小下标" ⟹ a* − 1 未达到 best
  ⟹ 任何收益为 best 的可行方案，其内存消耗都不可能 ≤ a* − 1
  ⟹ 所有 best 方案的内存消耗都 ≥ a*      （整数性：≤ a*−1 不成立 ⟹ ≥ a*）
下界方向：f[a*][B] == best ⟹ 确实存在一个内存不超过 a* 的 best 方案
两侧合并：该方案的内存恰好等于 a*        （≥ a* 且 ≤ a*）∎

1
2
3
4
5

best, mem, cal = f[A][B], 0, 0
while f[mem][B] < best:      # 先沿 a 夹：第一个达到 best 的 a 就是真实内存
    mem += 1
while f[mem][cal] < best:    # 锁定该行后再沿 b 夹（不能同时对两维夹，见 24.7）
    cal += 1

1
2
3
4
5
6
7
8

若在容量轴上原地滚动处理同一组的物品：
  for item in group:
      for j in range(C, c_item - 1, -1):
          f[j] = min(f[j], f[j - c_item] + t_item)
  处理组内第 2 件时，f[·] 里已经混入了"选了第 1 件"的状态，
  于是可能得到"同一组选了两件"的方案 —— 违反约束。
正确做法：每层新开一个数组 g，从 f 转移，处理完整组后再 f = g：
  g[j + c] = min(g[j + c], f[j] + t)     对组内每个物品、每个可行 j

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

INF = float('inf')

def group_knapsack_exact(cap, groups):
    """分组背包（每组恰好选一件），口径为"消耗恰好为 j"。
    groups[g] = [(cost, time), ...]，返回 (最小总耗时, 达到该耗时的最小消耗)。"""
    f = [INF] * (cap + 1)
    f[0] = 0                                  # 恰好口径：只有消耗 0 可达
    for group in groups:
        g = [INF] * (cap + 1)                 # 每层新开数组：原地滚动会让同组选到两件
        for j in range(cap + 1):
            if f[j] == INF: continue
            for cost, time in group:
                if j + cost <= cap and f[j] + time < g[j + cost]:
                    g[j + cost] = f[j] + time  # 源是 f（上一组），不是 g
        f = g
    # 升序扫描 + 严格小于：第一次取到最小耗时的 j 就是最省资源的方案
    best_time, best_cost = INF, 0
    for j in range(cap + 1):
        if f[j] < best_time:
            best_time, best_cost = f[j], j
    return best_time, best_cost

1
2
3
4
5

若 f[j] = 消耗不超过 j 时的最小耗时：
  f[j] 对所有 j ≥ 最优消耗 都等于同一个最小值（"不超过"是宽松的）
  ⟹ 消耗信息被抹掉 ⟹ 无法回答"实际消耗是多少"
若 f[j] = 消耗恰好为 j 时的最小耗时：
  每个 j 对应一个确切的消耗量 ⟹ 扫一遍就能在并列的最小耗时里挑出消耗最小的