BISHI136　【模板】01背包¶

简单通过率 36.44%python3样例通过牛客 AC

讲解章节：背包问题

一句话

同时求「不要求装满」和「恰好装满」两问。

解题思路¶

这题考什么¶

01 背包的一维滚动数组写法，以及「恰好装满」与「不要求装满」只差在初值这一经典对比。

f[c] = max(f[c], f[c - v] + w)     容量倒序遍历

不要求装满：f 全初始化为 0（任何容量都合法，初始价值 0）；
恰好装满： f[0] = 0，其余初始化为 -∞（表示「凑不出这个体积」）。

为什么必须倒序：f[c-v] 必须还是「上一轮（不含本物品）」的值，正序会让同一件物品被重复选（那是完全背包）。

数据规模与复杂度¶

n, V <= 1e3，O(nV) = 1e6，O(V) 空间——正好是题目备注要求的复杂度。

Python 关键¶

把内层的容量循环下沉到 C 层。一维倒序循环

for c in range(V, v-1, -1): f[c] = max(f[c], f[c-v]+w)

等价于一次「整段取 max」：

f[v:] = list(map(max, f[v:], [x + w for x in f[:V+1-v]]))

右边的候选数组是在赋值之前用旧的 f 算好的，所以 01 语义自动成立，而且列表推导式 + map 全在 C 层，比 1e6 次 Python 迭代快 5-8 倍。

坑在哪¶

「恰好装满」无解时输出 0（不是 -1、不是负数）；
-∞ 不能取 -1 这种「小负数」——加上 w 之后可能变成正数把答案带歪。这里取 -1e18，加满 1e3 个 1e3 也只是 -1e18+1e6，仍然远小于 0；
v_i >= 1，不用担心体积为 0 的自环。

参考实现¶

solutions/BISHI136.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); V = int(data[1])
    NEG = -(1 << 60)                         # 「凑不出」的哨兵，加法后仍远小于 0
    # 两问只差在初值：f1 全 0 表示「任何容量都是合法状态」；
    # f2 只有容量 0 合法，其余是 NEG，凑不出的体积永远传不出正值
    f1 = [0] * (V + 1)                       # 不要求装满
    f2 = [NEG] * (V + 1)                     # 恰好装满
    f2[0] = 0
    p = 2
    for _ in range(n):
        v = int(data[p]); w = int(data[p + 1])
        p += 2
        if v > V:                            # 单件就超容量，对两问都无用
            continue
        m = V + 1 - v                        # 候选段长度：源容量 0..V-v 对应目标 v..V
        # 等价于 for c in range(V, v-1, -1)。右侧的候选列表在赋值前一次算完，
        # 用的全是本物品未参与时的旧 f，所以「每件只用一次」的 01 语义自动成立
        f1[v:] = list(map(max, f1[v:], [x + w for x in f1[:m]]))
        f2[v:] = list(map(max, f2[v:], [x + w for x in f2[:m]]))
    # 恰好装满无解时 f2[V] 还是负的哨兵，按题意输出 0
    sys.stdout.write("%d\n%d\n" % (f1[V], f2[V] if f2[V] >= 0 else 0))


main()

BISHI136 【模板】01背包¶