经典背包问题 (Knapsack DP)

背包问题是动态规划中最经典、应用最广泛的基础模型。核心在于状态定义与容量遍历方向（倒序或正序）的选择，以及当约束扩展至依赖、分组或多重选择时的状态压缩与数学优化。

---

1. 0-1 背包问题

有 \(N\) 件物品和一个容量为 \(V\) 的背包。第 \(i\) 件物品的体积为 \(w_i\)，价值为 \(v_i\)。每种物品仅有 \(1\) 件，可选或不选。

状态定义与转移

• 定义 \(dp[i][j]\) 表示前 \(i\) 件物品放入容量为 \(j\) 的背包中所能获得的最大价值：

\[ dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w_i] + v_i) \quad (j \ge w_i) \]

一维空间优化与倒序遍历铁律

由于计算 \(dp[i][j]\) 仅依赖上一轮迭代的 \(dp[i - 1][j]\) 与 \(dp[i - 1][j - w_i]\)，我们可以压缩为一维数组 \(dp[j]\)。

• 倒序枚举铁律：容量 \(j\) 必须从 \(V\) 倒序遍历至 \(w_i\)。
• 数学本质：倒序遍历确保了在计算 \(dp[j]\) 时，所需的 \(dp[j - w_i]\) 依然保存着上一轮（即前 \(i-1\) 件物品）的状态，杜绝了单件物品被重复选取的可能。

#include <vector>
#include <algorithm>

// n: 物品数量, V: 背包容量
// w[i]: 体积, v[i]: 价值 (0-indexed)
long long knapsack_01(int n, int V, const std::vector<int>& w, const std::vector<long long>& v) {
    std::vector<long long> dp(V + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= w[i]; --j) {
            dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[V];
}

• 时间复杂度：\(\mathcal{O}(NV)\)
• 空间复杂度：\(\mathcal{O}(V)\)

---

2. 完全背包问题

有 \(N\) 种物品和一个容量为 \(V\) 的背包。每种物品有无限多件可用。

状态转移与正序遍历

与 0-1 背包唯一的差异在于：选取了第 \(i\) 种物品后，依然可以继续选取第 \(i\) 种物品。

• 二维转移方程：\(dp[i][j] = \max(dp[i - 1][j], dp[i][j - w_i] + v_i)\)
• 正序枚举铁律：一维滚动数组中，容量 \(j\) 必须从 \(w_i\) 正序遍历至 \(V\)。
• 数学本质：正序遍历时，较小的 \(dp[j - w_i]\) 已经包含了当前轮次选入的第 \(i\) 种物品，因此 \(dp[j]\) 可以在本轮累加中多次重复选入该物品。

long long knapsack_complete(int n, int V, const std::vector<int>& w, const std::vector<long long>& v) {
    std::vector<long long> dp(V + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = w[i]; j <= V; ++j) {
            dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[V];
}

• 时间复杂度：\(\mathcal{O}(NV)\)
• 空间复杂度：\(\mathcal{O}(V)\)

---

3. 多重背包问题

第 \(i\) 种物品最多有 \(c_i\) 件可用。

3.1 二进制分组拆分优化

直接朴素展开为单件物品的复杂度为 \(\mathcal{O}(V \sum c_i)\)。 利用二进制权值拆分：任何正整数 \(C\) 均可唯一拆分为 \(1, 2, 4, 8, \dots, 2^{k-1}\) 以及剩余余量 \(R = C - (2^k - 1)\) 的线性组合。 将数量为 \(c_i\) 的物品捆绑拆解成 \(\lfloor \log_2(c_i) \rfloor + 1\) 个复合单件，转化为 0-1 背包求解。

struct Item {
    int weight;
    long long val;
};

long long knapsack_multiple_binary(int V, const std::vector<int>& w, 
                                   const std::vector<long long>& v, 
                                   const std::vector<int>& c) {
    std::vector<Item> items;
    int n = w.size();

    // 二进制拆分
    for (int i = 0; i < n; ++i) {
        int count = c[i];
        int k = 1;
        while (count >= k) {
            items.push_back({w[i] * k, v[i] * k});
            count -= k;
            k <<= 1;
        }
        if (count > 0) {
            items.push_back({w[i] * count, v[i] * count});
        }
    }

    // 转化为标准 0-1 背包
    std::vector<long long> dp(V + 1, 0);
    for (const auto& item : items) {
        for (int j = V; j >= item.weight; --j) {
            dp[j] = std::max(dp[j], dp[j - item.weight] + item.val);
        }
    }
    return dp[V];
}

• 时间复杂度：\(\mathcal{O}(V \sum \log c_i)\)
• 空间复杂度：\(\mathcal{O}(V + \sum \log c_i)\)

3.2 单调队列优化 (理论极限 O(NV))

按容量对物品体积 \(w\) 的余数 \(r \in [0, w - 1]\) 划分子问题：所有形如 \(j = k \cdot w + r\) 的状态仅在同余系内相互转移。 令 \(dp[k \cdot w + r] = \max_{0 \le p \le c} \{ dp[(k - p) \cdot w + r] + p \cdot v \}\)。 通过移项将常数分离，转化为标准的滑动窗口滑动最值模型，使用单调双端队列在 \(\mathcal{O}(1)\) 摊还时间内滑动维护窗口极值，将整体多重背包总复杂度彻底压制到严格 \(\mathcal{O}(NV)\)。

---

4. 分组背包问题 (Group Knapsack)

物品被划分为 \(K\) 个互斥组，每组内至多只能选择一件物品（或者恰好选一件）。

循环顺序的三重嵌套铁律

1. 外层循环：枚举每个分组 \(k \in [1, K]\)；
2. 中层循环：倒序枚举背包容量 \(j\)（从 \(V\) 到 \(0\)）；

3. 内层循环：枚举当前组内的所有物品 \(i \in \text{group}[k]\)。

4. 核心警示：容量循环必须在外，组内物品循环必须在内！如果颠倒这两层循环，会导致同一组内的多个物品被分别放入同一个容量状态中，彻底破坏“组内至多选一件”的互斥约束！

struct GroupItem {
    int weight;
    long long val;
};

long long knapsack_group(int V, const std::vector<std::vector<GroupItem>>& groups) {
    std::vector<long long> dp(V + 1, 0);
    for (const auto& group : groups) {
        for (int j = V; j >= 0; --j) {
            for (const auto& item : group) {
                if (j >= item.weight) {
                    dp[j] = std::max(dp[j], dp[j - item.weight] + item.val);
                }
            }
        }
    }
    return dp[V];
}

---

5. 二维费用、方案统计与三大边界模型

5.1 二维费用背包

每件物品不仅消耗体积 \(w_i\)，还消耗质量/其他维度资源 \(m_i\)。

• 只需将一维数组扩展为二维滚动矩阵 \(dp[j][k]\)，两维容量均按 0-1 背包原则从大到小倒序遍历：

\[ dp[j][k] = \max(dp[j][k], dp[j - w_i][k - m_i] + v_i) \]

5.2 方案数统计：组合数 vs 排列数的循环顺序铁律

在计数型背包中，外层循环与内层循环的嵌套顺序直接决定了统计出来的是组合数还是排列数：

graph TD
    subgraph "组合数 (无序: [1, 2] 与 [2, 1] 视为同一种)"
    A1["外层循环: 遍历物品 coins"] --> A2["内层循环: 遍历容量 j"]
    A2 --> A3["原理: 物品加入的顺序被固化, 不可能出现顺序颠倒的重复组合!"]
    end

    subgraph "排列数 (有序: [1, 2] 与 [2, 1] 视为不同方案)"
    B1["外层循环: 遍历容量 j"] --> B2["内层循环: 遍历物品 coins"]
    B2 --> B3["原理: 每个容量状态都可以自由挑选任意物品作为结尾, 自动枚举全排列!"]
    end

• 求组合数（顺序无关）：物品在外层，容量在内层（经典题：LeetCode 518. 零钱兑换 II）；
• 求排列数（顺序相关）：容量在外层，物品在内层（经典题：LeetCode 377. 组合总和 Ⅳ）。

---

5.3 三大边界模型：至多、恰好与至少的初始化与转移

背包问题在不同题意下有三种截然不同的容量限制，初学者最容易在初始化与越界处理上犯错：

约束类型	语义描述	初始化方法	越界与转移处理
至多装满 \(V\)	总体积不超过 \(V\) 时的最大价值	\(dp[0 \dots V] = 0\)	\(j < w_i\) 时无法装入，正常截止到 \(w_i\)
恰好装满 \(V\)	总体积必须严格等于 \(V\)	\(dp[0] = 0\)，其余 \(dp[1 \dots V] = -\infty\) (求最大) 或 \(+\infty\) (求最小)	只有由合法状态转移而来的才合法，最终检查 \(dp[V]\) 是否仍为初始无效值
至少装满 \(V\)	总体积必须达到或超过 \(V\) 时的最小代价	\(dp[0] = 0\)，其余 \(dp[1 \dots V] = +\infty\)	容量下界截断：当 \(j - w_i < 0\) 时，转移到 \(dp[0]\)：\(dp[j] = \min(dp[j], dp[\max(0, j - w_i)] + v_i)\)

[!TIP] “至少装满”的边界截断直觉：如果一件物品的收益已经超过了当前子目标 \(j\)（即 \(j - w_i < 0\)），它依然是一个有效选择，且直接超额达标，其前置状态等价于“已经达成 0 目标”（即 \(dp[0]\)）。代表例题为 LeetCode 879. 盈利计划。

---

6. 有依赖的背包问题 (树上背包 DP)

在树形结构中，选择某个子节点物品的前提是必须同时选择其所有祖先节点（如大学课程先修依赖、选课问题）。

6.1 树上背包的状态定义与转移

设树以节点 \(u\) 为根，第 \(u\) 个节点的体积为 \(w_u\)，价值为 \(v_u\)。 - 定义 \(dp[u][j]\) 表示在以 \(u\) 为根的子树中选择物品、且总占用容量为 \(j\) 时所能获得的最大价值； - 必须强制先选择根节点 \(u\)：\(dp[u][w_u \dots V] = v_u\)； - 遍历 \(u\) 的每一个子节点 \(v\) 时，相当于将子树 \(v\) 作为一个分组背包合并进来：

\[ dp[u][j] = \max_{0 \le k \le j - w_u} \{ dp[u][j - k] + dp[v][k] \} \]

6.2 树上背包的复杂度优化 (上下界截断)

朴素树上背包合并三重循环的复杂度为 \(\mathcal{O}(N V^2)\)。通过引入子树大小（Subtree Size）上下界优化，可以将其严格压制到 \(\mathcal{O}(NV)\)：

#include <vector>
#include <algorithm>

// u: 当前根节点, V: 背包最大容量
// adj: 树的邻接表, w[u]: 体积, v[u]: 价值
void tree_knapsack_dfs(int u, int V, const std::vector<std::vector<int>>& adj, 
                       const std::vector<int>& w, const std::vector<int>& v,
                       std::vector<std::vector<int>>& dp, std::vector<int>& sz) {
    // 强制先选根节点 u
    sz[u] = w[u];
    dp[u][w[u]] = v[u];

    for (int child : adj[u]) {
        tree_knapsack_dfs(child, V, adj, w, v, dp, sz);

        // 倒序枚举当前 u 已占用的容量上限，利用 min(V, sz[u] + sz[child]) 严格限制循环上界
        int limit = std::min(V, sz[u] + sz[child]);
        for (int j = limit; j >= w[u]; --j) {
            // 枚举分配给子节点 child 的容量 k
            int k_max = std::min(j - w[u], sz[child]);
            for (int k = 1; k <= k_max; ++k) {
                if (dp[u][j - k] > 0 && dp[child][k] > 0) {
                    dp[u][j] = std::max(dp[u][j], dp[u][j - k] + dp[child][k]);
                }
            }
        }
        sz[u] += sz[child];
    }
}

• 数学证明：上下界循环的实质等价于枚举子树内的所有点对 \((x, y)\)，每个点对只在其最近公共祖先（LCA）处被合并一次。因此总时间复杂度由 \(\mathcal{O}(NV^2)\) 骤降为严格的 \(\mathcal{O}(NV)\)！

---

7. 背包的最优方案路径还原 (Path Reconstruction)

面试中常常要求：不仅要求出最大价值，还要输出具体选择了哪些物品。

7.1 利用二维表格回溯倒推

若在求解时保留了二维状态矩阵 \(dp[i][j]\)： - 从最后一件物品 \(i = N\)、最终容量 \(j = V\) 往前倒推： 1. 若 \(dp[i][j] == dp[i - 1][j]\)：说明没有选择第 \(i\) 件物品，状态由 \(dp[i-1][j]\) 转移而来，继续考察 \(i - 1\)； 2. 若 \(j \ge w_i\) 且 \(dp[i][j] == dp[i - 1][j - w_i] + v_i\)：说明选择了第 \(i\) 件物品！记录编号 \(i\)，容量更新为 \(j = j - w_i\)，继续考察 \(i - 1\)。

7.2 字典序最小/最大方案还原技巧

• 若题目要求输出字典序最小的物品编号序列：
• 可以将物品逆序处理（从第 \(N\) 件推到第 \(1\) 件），这样在正序还原时优先选择下标小的物品；
• 代表例题为 LeetCode 1449. 数位成本和为目标值的最大数字。

---

8. 超大容量背包与折半搜索 (Meet-in-the-Middle)

当物品数量较少（如 \(N \le 40\)），但背包容量极其庞大（如 \(V = 10^{14}\)，或者物品体积和目标值高达 \(10^9\)）时，任何基于容量的 DP 数组都将因空间溢出而彻底失效。

8.1 折半搜索算法流程

1. 对半分治：将 \(N\) 个物品均分为两半 \(A\)（前 \(N/2\) 个）和 \(B\)（后 \(N - N/2\) 个）；
2. 生成子集状态：
3. 暴力递归生成集合 \(A\) 的所有 \(2^{N/2}\) 种组合的 (体积, 价值)，存入列表 \(L_1\)；
4. 同样生成集合 \(B\) 的所有 \(2^{N - N/2}\) 种组合，存入列表 \(L_2\)；
5. 当 \(N = 40\) 时，单侧只有 \(2^{20} \approx 10^6\) 种状态，内存与时间完全可承受！
6. 单调性剪枝与排序：
7. 将 \(L_2\) 按照体积升序排序；
8. 剔除无效冗余状态：若体积更大但价值反而更小，直接丢弃，使 \(L_2\) 的体积与价值均保持严格单调递增；
9. 二分查找匹配：
10. 遍历 \(L_1\) 中的每个状态 \((w_1, v_1)\)，在 \(L_2\) 中通过二分查找（std::upper_bound）寻找满足 \(w_2 \le V - w_1\) 的最大可能 \(v_2\)；
11. 总时间复杂度为 \(\mathcal{O}(N \cdot 2^{N/2})\)，成功攻克万亿级容量超大背包！

---

9. LeetCode 经典真题精选与题解提示

9.1 0-1 背包可行性与计数

• LeetCode 416 - 分割等和子集 (Partition Equal Subset Sum) 中等

  提示

  0-1 背包可行性判定。 - 数组总和如果为奇数直接返回 false。目标为选取子集使其和恰好为 \(target = sum / 2\)。 - 布尔型 0-1 背包：dp[j] = dp[j] || dp[j - num]。容量倒序遍历；若 dp[target] 变真可提前退出。可用 std::bitset<10001> 位运算加速达到 64 倍常数优化。

• LeetCode 1049 - 最后一块石头的重量 II (Last Stone Weight II) 中等

  提示

  0-1 背包最值转化。 - 任意两两粉碎操作的实质，是将所有石头分为两堆，最终结果为两堆重量差 \(|S_1 - S_2|\)； - 要使差值最小，应让较小的那一堆重量尽可能接近 \(sum / 2\)； - 转化为背包容量为 \(V = \lfloor sum / 2 \rfloor\) 的经典 0-1 背包，求能装入的最大重量 \(dp[V]\)。答案即为 \(sum - 2 \times dp[V]\)。

• LeetCode 494 - 目标和 (Target Sum) 中等

  提示

  0-1 背包方案数。 - 设正号集合和为 \(P\)，负号集合和为 \(N\)。有 \(P - N = target\) 且 \(P + N = sum\)； - 相加得 \(2P = target + sum \implies P = (target + sum) / 2\)。若 \((target + sum)\) 为奇数或小于 0 则无解； - 转化为从数组中挑选若干数使和恰为 \(P\) 的 0-1 背包方案数计数，容量倒序遍历累加方案。

---

9.2 完全背包求最值、组合数与排列数

• LeetCode 322 - 零钱兑换 (Coin Change) 中等

  提示

  完全背包求最小物品数。 - 每种面值硬币无限多，初始化 \(dp[0] = 0\)，其余为正无穷； - 容量正序遍历：dp[j] = min(dp[j], dp[j - coin] + 1)。最终检查 \(dp[amount]\) 是否仍为无穷大。

• LeetCode 279 - 完全平方数 (Perfect Squares) 中等

  提示

  完全背包求最少平方数个数。 - 物品为所有不超过 \(n\) 的完全平方数 \(1, 4, 9, 16 \dots\)； - 初始化 \(dp[0] = 0\)，其余为正无穷。正序遍历容量：dp[j] = min(dp[j], dp[j - i * i] + 1)。

• LeetCode 518 - 零钱兑换 II (Coin Change II) 中等

  提示

  完全背包求组合数（顺序无关）。 - 外层遍历硬币，内层正序遍历容量：dp[j] += dp[j - coin]； - 必须严格遵循外层固定硬币的顺序，彻底规避因排列引起的重复计数。

• LeetCode 377 - 组合总和 Ⅳ (Combination Sum IV) 中等

  提示

  完全背包求排列数（顺序有关）。 - 题目明确说明 (1, 2) 和 (2, 1) 属于不同组合，本质是求排列数； - 外层正序遍历容量，内层遍历物品：dp[j] += dp[j - num]； - 状态定义：\(dp[j]\) 表示装满容量 \(j\) 的所有可能排列数。注意 C++ 中相加可能爆 int，需配合 unsigned long long 防溢出。

---

9.3 二维费用与分组背包

• LeetCode 474 - 一和零 (Ones and Zeroes) 中等

  提示

  二维费用 0-1 背包。 - 统计每个字符串中包含的 0 的数量 \(zeros\) 和 1 的数量 \(ones\)； - 二维数组 \(dp[i][j]\) 表示至多 \(i\) 个 0 和 \(j\) 个 1 时能选取的最大字符串数量； - 双重倒序遍历容量：dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)。

• LeetCode 1155 - 掷骰子等于目标和的方法数 (Number of Dice Rolls With Target Sum) 中等

  提示

  分组背包恰好选一件模型。 - 共 \(n\) 个骰子对应 \(n\) 个分组，每个骰子必须且仅能投掷出 \(1 \sim k\) 点中的一个点数； - 外层枚举骰子分组，中层倒序枚举总和容量，内层枚举当前骰子的点数 \(1 \sim k\)。

• LeetCode 2218 - 从栈中取出 K 个硬币的最大面值和 (Maximum Value of K Coins From Piles) 困难

  提示

  前缀和 + 分组背包。 - 每个栈只能从顶部向下连续取硬币，取 \(x\) 个硬币的面值等于该栈的前缀和 \(pref[x]\)； - 每个栈构成一个互斥组，在组内选择取 \(0, 1, 2 \dots \min(k, len)\) 枚硬币（至多选一种决策）； - 外层遍历栈分组，中层倒序遍历总硬币容量 \(j \in [1, k]\)，内层遍历当前栈抽取的硬币数 \(x\)。

---

9.4 差值状态、下界模型与超大容量

• LeetCode 879 - 盈利计划 (Profitable Schemes) 困难

  提示

  二维费用 + 收益下界截断背包。 - 状态定义：\(dp[j][k]\) 表示使用不超过 \(j\) 名员工、创造至少 \(k\) 利润的计划数； - 利润下界截断：新利润超出 \(minProfit\) 依然合法，转移时取 \(\max(0, k - profit)\)；双重倒序遍历人数与利润。

• LeetCode 956 - 最高的广告牌 (Tallest Billboard) 困难

  提示

  差值背包 DP。 - 将钢筋分为两堆，要求两堆高度相等，求最大高度。等价于：每根钢筋可以有三种选择（放入第一堆加、放入第二堆减、不选）； - 状态定义：\(dp[diff]\) 表示两堆高度差为 \(diff\) 时，较矮那根钢筋的最大可能高度； - 遍历钢筋 \(len\) 时转移分三种：不选；加到较高的一侧（差值变为 \(diff + len\)）；加到较矮的一侧（若超过较高一侧产生反转，差值变为 \(|diff - len|\)）。

• LeetCode 1449 - 数位成本和为目标值的最大数字 (Form Largest Integer With Digits That Add up to Target) 困难

  提示

  完全背包恰好装满 + 字典序最大路径还原。 - 每种数字 1~9 有各自花费 \(cost[d]\)，且可无限次重复使用； - 先用完全背包求出恰好花完 \(target\) 成本能组成的最大数字位数：\(dp[j] = \max(dp[j], dp[j - cost[d]] + 1)\)； - 若 \(dp[target] < 0\) 说明无法拼出；否则从数字 9 倒序遍历到 1，若 \(target \ge cost[d]\) 且 \(dp[target] == dp[target - cost[d]] + 1\)，则贪心选择数字 \(d\) 输出，并令 \(target -= cost[d]\)。

• LeetCode 1755 - 最接近目标值的子序列和 (Closest Subsequence Sum) 困难

  提示

  超大容量背包 + 折半搜索 (Meet-in-the-Middle)。 - 数组长度 \(n \le 40\)，但数值跨度极大（目标和可达 \(10^9\)），无法开辟 DP 数组； - 将数组分成两半，各自生成所有子序列和，对后半部分排序去重，遍历前半部分在后半部分中二分查找最接近目标的组合。