背包问题全解

背包问题（Knapsack Problem）是一类经典的组合优化问题。核心场景是：在有限的资源（背包容量）约束下，选择物品以实现某个目标（如总价值最大、总成本最小）。它在资源分配、投资决策、货物装载、模型量化等领域有广泛应用。

按照物品的可用数量和组织方式，背包问题有四种核心变体：

所有变体的状态定义都是：dp[i][j] 表示考虑前 $i$ 个物品（或前 $i$ 组），在容量为 $j$ 时的最优值。递推时只需按每种变体的约束调整转移方程即可。

二维 DP 解法

状态定义：$dp[i][j]$ 表示考虑前 $i$ 件物品，在背包容量为 $j$ 时能获得的最大价值。

对于第 $i$ 件物品，有两种决策：

• 不选：$dp[i][j] = dp[i-1][j]$
• 选（需 $j \ge w_i$）：$dp[i][j] = dp[i-1][j - w_i] + v_i$

最终答案：$dp[N][V]$。初始条件：$dp[0][j] = 0$。

def knapsack_01_2d(N, V, weights, values):
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = weights[i-1], values[i-1]
        for j in range(V + 1):
            dp[i][j] = dp[i-1][j]               # 不选
            if j >= w:
                dp[i][j] = max(dp[i][j], dp[i-1][j - w] + v)
    return dp[N][V]
  

空间复杂度 $O(NV)$，时间复杂度 $O(NV)$。

滚动数组优化（一维 DP）

观察转移方程发现：$dp[i][j]$ 只依赖 $dp[i-1][\cdot]$（上一行的数据）。可以用一个一维数组 dp[j] 滚动覆盖，将空间降到 $O(V)$。

关键细节：背包容量 $j$ 必须 倒序 遍历（从 $V$ 到 $w_i$）。如果正序遍历，$dp[j - w_i]$ 可能已经被当前物品更新过，导致同一件物品被多次放入。

def knapsack_01_1d(N, V, weights, values):
    dp = [0] * (V + 1)
    for i in range(N):
        w, v = weights[i], values[i]
        for j in range(V, w - 1, -1):          # 倒序遍历！
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[V]
  

空间 $O(V)$，时间 $O(NV)$。

与 0-1 背包的唯一区别

完全背包的状态转移方程在形式上与 0-1 背包几乎一样，唯一的区别是 遍历顺序：

• 0-1 背包：内层循环 倒序（确保每件物品只取一次）
• 完全背包：内层循环 正序（允许同种物品多次取）

正序遍历时，$dp[j - w_i]$ 可能已经包含了同一个物品 $i$ 被多次选取后的最优值，从而自动支持无限次选择。

def knapsack_complete(N, V, weights, values):
    dp = [0] * (V + 1)
    for i in range(N):
        w, v = weights[i], values[i]
        for j in range(w, V + 1):              # 正序遍历！
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[V]
  

一个更直观的理解：完全背包的 $dp[j]$ 表示"容量为 j 时能装的最大价值，物品可以重复使用"，相当于在每次决策时都允许从同一个物品中再拿一个。

最朴素的做法是直接把每件物品拆成 $c_i$ 个独立的 0-1 物品，复杂度 $O(V \sum c_i)$，当 $c_i$ 很大时会超时。

二进制优化

核心思想：将 $c_i$ 件相同的物品拆成若干组，每组包含 $1, 2, 4, \ldots, 2^k, r$ 件（$r = c_i - (2^{k+1}-1)$），即用二进制分解来覆盖 $[0, c_i]$ 内的任意取值。这样每组就是一个 0-1 物品，组数从 $c_i$ 降到 $O(\log c_i)$。

def knapsack_multi(N, V, weights, values, counts):
    """多重背包：二进制优化"""
    items = []  # (weight, value) 列表，展开后的 0-1 物品
    for i in range(N):
        w, v, c = weights[i], values[i], counts[i]
        k = 1
        while k <= c:
            items.append((w * k, v * k))
            c -= k
            k <<= 1
        if c > 0:
            items.append((w * c, v * c))

    # 对展开后的物品做 0-1 背包
    dp = [0] * (V + 1)
    for w, v in items:
        for j in range(V, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[V]
  

时间复杂度 $O(V \sum \log c_i)$，空间 $O(V)$。

解法

套一层"组"的外循环，内层对容量倒序遍历，再遍历组内所有物品做决策：

def knapsack_group(groups, V):
    """
    groups: list of list of (weight, value)
    """
    dp = [0] * (V + 1)
    for group in groups:
        for j in range(V, -1, -1):              # 容量倒序
            for w, v in group:                  # 尝试组内每个物品
                if j >= w:
                    dp[j] = max(dp[j], dp[j - w] + v)
    return dp[V]
  

如果题目要求每组 恰好 选一个，只需将初始化改为 $dp[0] = 0$ 且 $dp[1..V] = -\infty$，然后每组做一次"必须选一个"的转移（类似下面的实战例题）。

这是一个典型的 费用约束型背包——约束条件不再是"重量不超过容量"，而是"精度损失不超过 T"。每层必须在多种量化方案中选择一种（且只能选一种），目标从"价值最大"变成了"内存最小"。

问题转化

• 每层 $\to$ 一个 分组（必须选且仅选一个方案）
• 每种量化方案 $\to$ 一个物品（精度损失 = 重量，内存占用 = 价值）
• 精度损失阈值 $T$ $\to$ 背包容量
• 最小化总内存 $\to$ 求 dp 数组中的最小值

状态定义：$dp[j]$ 表示精度损失恰好为 $j$ 时的最小内存占用。

精度损失是浮点数。为了 DP，需要离散化：将损失乘以 100 转为整数，或者用哈希表（字典）记录所有可达的损失值。

Python 实现（字典 DP）

from collections import defaultdict

def solve():
    L, T = input().split()
    L, T = int(L), float(T)

    # dp: {精度损失: 最小内存占用}
    dp = {0.0: 0.0}

    for _ in range(L):
        parts = input().split()
        K = int(parts[0])
        options = []
        for i in range(K):
            bit = parts[1 + i * 3]    # "8bit" / "16bit"
            loss = float(parts[2 + i * 3])
            mem = float(parts[3 + i * 3])
            options.append((loss, mem))

        new_dp = defaultdict(lambda: float('inf'))
        for cur_loss, cur_mem in dp.items():
            for loss, mem in options:
                next_loss = cur_loss + loss
                if next_loss <= T + 1e-9:   # 浮点数精度
                    new_dp[next_loss] = min(
                        new_dp[next_loss],
                        cur_mem + mem
                    )
        dp = new_dp

    ans = min(dp.values())
    print(f"{ans:.2f}")
  

如果精度损失是两位小数（通常如此），也可以用整数 DP：将 $T$ 和所有 loss 乘以 100 转为整数处理，效率更高且无浮点精度问题。

样例推演

样例 1：

3 层，$T = 0.3$。每层量化方案如下：

最优选择：Layer 1=16bit, Layer 2=16bit, Layer 3=8bit

• 总精度损失 = $0.1 + 0.1 + 0.1 = 0.3 \le T$
• 总内存占用 = $200 + 300 + 150 = 650$

样例 2：

2 层，$T = 0.5$。全部选 8bit：loss = $0.2 + 0.3 = 0.5 \le 0.5$，mem = $100 + 150 = 250$。

与背包模型的对应

回顾一下，这道题的本质是 分组背包 + 最小化目标：

这种转化能力才是背包问题真正有价值的地方——把实际问题中的资源约束、成本、收益映射到背包的状态空间上，然后套用成熟的 DP 框架求解。

背包问题的本质是一个 二维 DP 模板，所有变体都可以用同一套框架表达：

# 模板框架
dp = [0] * (V + 1)    # 一维滚动数组

for item in items:                          # 循环物品/组
    # 0-1 背包: j 倒序
    # 完全背包: j 正序
    # 分组背包: j 倒序, 内层遍历组内物品
    for j in range(...):
        dp[j] = max/min(dp[j], dp[j - w] + v)
  

棋盘上每一枚棋子的移动路径不同，但下棋的思考方式是一致的——看透问题背后的"资源-成本-目标"三角关系，套上背包模板，写出转移方程，调整遍历顺序。理解这一点，任何"背包"题都不会是难题。