跳转至

经典背包问题 (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 单调队列优化（理论极限 \(\mathcal{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 背包方案数统计

求恰好装满容量 \(V\) 的方案总数（加法原理）：

  • 初始化：\(dp[0] = 1\)，其余均为 \(0\)；
  • 转移方程：\(dp[j] = (dp[j] + dp[j - w_i]) \pmod M\)；
  • 若求排列数（顺序有关）：容量在外层循环，物品在内层循环；
  • 若求组合数（顺序无关）：物品在外层循环，容量在内层循环。

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

  • 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 位运算加速达到 64 倍常数优化。

  • 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 背包方案数计数。

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

    提示

    完全背包求最小硬币数。

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

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

    提示

    完全背包求组合数（顺序无关）。

    • 硬币在外层遍历，容量在内层正序遍历：dp[j] += dp[j - coin]。外层固定硬币顺序彻底规避排列重复。

  • 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\) 点中的一个点数。
    • 属于“每组必须恰好选一件”的分组背包模型。状态转移中加入模数运算。