背包 DP

背包 DP（Knapsack DP）

背包 DP（Knapsack DP）是一类经典动态规划问题，核心是在容量限制下进行选择决策，以达到最优目标（如最大价值、方案数等）。

这类问题的基本形式为：

每个物品具有重量 w[i]和价值 v[i]（可选取的次数 k[i]）
背包容量为 W
通过选择物品，使目标函数最优

根据每个物品可选取的次数，背包问题主要分为：

类型	选择次数	二维转移依赖	一维遍历顺序
0-1 背包	≤1 次	`dp[i-1][...]`	逆序 → 使用上一层状态
完全背包	无限次	`dp[i][...]`	正序 → 使用当前层状态
多重背包	≤ `k[i]` 次	`dp[i-1][...]`	逆序 + 枚举次数 / 二进制拆分 / 单调队列

0-1 背包

问题描述

有 n 件物品，每件物品有重量 w[i] 和价值 v[i]。背包容量为 W，每件物品只能选或不选，求最大价值。

状态定义

dp[i][j] = 前 i 个物品，容量为 j 时的最大价值

状态转移方程

选择	状态转移公式
不选第 i 个物品	`dp[i][j] = dp[i-1][j]`
选第 i 个物品	`dp[i][j] = dp[i-1][j-w[i]] + v[i]`
✅ 合并	`dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])`

其中第一项表示不选第 i 件，第二项表示选第 i 件（前提是 j >= w[i]）

PythonC++Rust

def knapsack(W: int, weights: list, values: list) -> int:
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= weights[i - 1]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
    return dp[n][W]

int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i - 1]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][W];
}

fn knapsack(W: i32, weights: &[i32], values: &[i32]) -> i32 {
    let n = weights.len();
    let mut dp = vec![vec![0; W as usize + 1]; n + 1];
    for i in 1..=n {
        for j in 0..=W {
            dp[i][j] = dp[i - 1][j];
            if j >= weights[i - 1] {
                dp[i][j] = dp[i][j].max(dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    dp[n][W as usize]
}

空间优化

二维空间优化为一维空间

由于 dp[i][j] 只依赖 dp[i-1][...]，可以压缩为一维数组。注意内层循环必须逆序遍历，以避免同一轮中重复使用已更新的值。

方式	状态转移方程	说明
二维（未压缩）	`dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])`	只依赖上一层 `dp[i-1][...]`
一维（压缩后）	`dp[j] = max(dp[j], dp[j-w[i]] + v[i])`	必须内层 `j` 逆序以防重复选取

PythonC++Rust

def knapsack_optimized(W: int, weights: list, values: list) -> int:
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

int knapsack_optimized(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = W; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

fn knapsack_optimized(W: i32, weights: &[i32], values: &[i32]) -> i32 {
    let n = weights.len();
    let mut dp = vec![0; W as usize + 1];
    for i in 0..n {
        for j in (weights[i]..=W).rev() {
            dp[j as usize] = max(dp[j as usize], dp[j as usize - weights[i] as usize] + values[i]);
        }
    }
    dp[W as usize]
}

完全背包

问题描述

有 n 件物品，每件物品有重量 w[i] 和价值 v[i]。背包容量为 W，每件物品可以选无限次，求最大价值。

状态定义

dp[i][j] = 前 i 个物品，容量为 j 时的最大价值

状态转移方程

选择	状态转移公式
不选第 i 个物品	`dp[i][j] = dp[i-1][j]`
选第 i 个物品	`dp[i][j] = dp[i][j-w[i]] + v[i]`
✅ 合并	`dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])`

完全背包与 0-1 背包的区别

注意这里与 0-1 背包的区别在于：

0-1 背包：选当前物品后，转移到 dp[i-1][j-w[i]]
完全背包：选当前物品后，转移到 dp[i][j-w[i]]

因为同一件物品可以重复选，所以仍然留在第 i 层。

PythonC++Rust

def complete_knapsack(W: int, weights: list, values: list) -> int:
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(W + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= weights[i - 1]:
                dp[i][j] = max(dp[i][j], dp[i][j - weights[i - 1]] + values[i - 1])

    return dp[n][W]

int complete_knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i - 1]) {
                dp[i][j] = max(dp[i][j], dp[i][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[n][W];
}

fn complete_knapsack(W: usize, weights: &[usize], values: &[i32]) -> i32 {
    let n = weights.len();
    let mut dp = vec![vec![0; W + 1]; n + 1];

    for i in 1..=n {
        for j in 0..=W {
            dp[i][j] = dp[i - 1][j];
            if j >= weights[i - 1] {
                dp[i][j] = dp[i][j].max(dp[i][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    dp[n][W]
}

空间优化

二维空间优化为一维空间

由于 dp[i][j] 只依赖当前层左侧状态 dp[i][j-w[i]] 和上一层状态 dp[i-1][j]，可以压缩为一维数组。注意内层循环必须正序遍历，这样才能在同一轮中重复使用当前物品。

方式	状态转移方程	说明
二维(未压缩)	`dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])`	选当前物品后仍停留在第 `i` 层
一维(压缩后)	`dp[j] = max(dp[j], dp[j-w[i]] + v[i])`	必须内层 `j` 正序，允许重复选取

PythonC++Rust

def complete_knapsack_optimized(W: int, weights: list, values: list) -> int:
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        for j in range(weights[i], W + 1):  # 正序遍历
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

    return dp[W]

int complete_knapsack_optimized(int W, vector<int>& weights, vector<int>& values) {
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < weights.size(); i++) {
        for (int j = weights[i]; j <= W; j++) {  // 正序遍历
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    return dp[W];
}

fn complete_knapsack_optimized(W: usize, weights: &[usize], values: &[i32]) -> i32 {
    let mut dp = vec![0; W + 1];

    for i in 0..weights.len() {
        for j in weights[i]..=W {
            dp[j] = dp[j].max(dp[j - weights[i]] + values[i]);
        }
    }

    dp[W]
}

多重背包

问题描述

有 n 件物品，每件物品有重量 w[i]、价值 v[i] 和数量上限 k[i]。背包容量为 W，每件物品最多选 k[i] 次，求最大价值。

多重背包与 0-1 / 完全背包的关系

类型	选择次数	本质
0-1 背包	≤1 次	多重背包中 `k[i] = 1` 的特例
完全背包	无限次	多重背包中 `k[i] = ∞` 的特例
多重背包	≤ `k[i]` 次	一般情况

状态定义

dp[i][j] = 前 i 个物品，容量为 j 时的最大价值

状态转移方程

对于第 i 个物品，可以选 0, 1, 2, ..., k[i] 次：

\[ dp[i][j] = \max_{0 \le t \le k[i]} \{ dp[i-1][j - t \cdot w[i]] + t \cdot v[i] \} \quad (j \ge t \cdot w[i]) \]

朴素做法

最直接的思路是在 0-1 背包基础上，对每个物品枚举选取次数 t。

时间复杂度：\(O(n \cdot W \cdot \sum k[i])\)
空间复杂度：\(O(W)\)（一维优化后）

PythonC++Rust

def multiple_knapsack_naive(W: int, weights: list, values: list, counts: list) -> int:
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, weights[i] - 1, -1):  # 逆序，同 0-1 背包
            for t in range(1, counts[i] + 1):
                if j >= t * weights[i]:
                    dp[j] = max(dp[j], dp[j - t * weights[i]] + t * values[i])
    return dp[W]

int multiple_knapsack_naive(int W, vector<int>& weights, vector<int>& values, vector<int>& counts) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = W; j >= weights[i]; j--) {
            for (int t = 1; t <= counts[i] && t * weights[i] <= j; t++) {
                dp[j] = max(dp[j], dp[j - t * weights[i]] + t * values[i]);
            }
        }
    }
    return dp[W];
}

fn multiple_knapsack_naive(w_cap: usize, weights: &[usize], values: &[i32], counts: &[usize]) -> i32 {
    let n = weights.len();
    let mut dp = vec![0; w_cap + 1];
    for i in 0..n {
        for j in (weights[i]..=w_cap).rev() {
            for t in 1..=counts[i] {
                if t * weights[i] <= j {
                    dp[j] = dp[j].max(dp[j - t * weights[i]] + t as i32 * values[i]);
                }
            }
        }
    }
    dp[w_cap]
}

二进制拆分优化

核心思想

朴素做法对每个物品枚举 k[i] 次，当 k[i] 很大时效率低下。

二进制拆分利用了一个事实：任何整数 k 都可以用 1, 2, 4, ..., 2^p, r 这些数的子集和来表示 0 ~ k 中的所有整数（其中 r = k - 2^{p+1} + 1）。

因此，将第 i 个物品（数量 k[i]）拆分为 \(O(\log k[i])\) 个「虚拟物品」，每个虚拟物品只选或不选，转化为 0-1 背包。

拆分示例

k[i] = 13 → 拆为 1, 2, 4, 6（因为 1+2+4 = 7, r = 13 - 7 = 6），这 4 个数的子集和可以表示 0 ~ 13 的所有整数。

同理：

6 = 1 + 2 + 3
8 = 1 + 2 + 4 + 1
18 = 1 + 2 + 4 + 8 + 3
31 = 1 + 2 + 4 + 8 + 16

时间复杂度：\(O(W \cdot \sum \log k[i])\)
空间复杂度：\(O(W)\)

PythonC++Rust

def multiple_knapsack_binary(W: int, weights: list, values: list, counts: list) -> int:
    # 二进制拆分，转化为 0-1 背包
    new_w, new_v = [], []
    for i in range(len(weights)):
        remain = counts[i]
        k = 1
        while k <= remain:
            new_w.append(k * weights[i])
            new_v.append(k * values[i])
            remain -= k
            k *= 2
        if remain > 0:
            new_w.append(remain * weights[i])
            new_v.append(remain * values[i])

    # 标准 0-1 背包
    dp = [0] * (W + 1)
    for i in range(len(new_w)):
        for j in range(W, new_w[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - new_w[i]] + new_v[i])
    return dp[W]

int multiple_knapsack_binary(int W, vector<int>& weights, vector<int>& values, vector<int>& counts) {
    vector<int> new_w, new_v;
    for (int i = 0; i < weights.size(); i++) {
        int remain = counts[i], k = 1;
        while (k <= remain) {
            new_w.push_back(k * weights[i]);
            new_v.push_back(k * values[i]);
            remain -= k;
            k *= 2;
        }
        if (remain > 0) {
            new_w.push_back(remain * weights[i]);
            new_v.push_back(remain * values[i]);
        }
    }

    vector<int> dp(W + 1, 0);
    for (int i = 0; i < new_w.size(); i++) {
        for (int j = W; j >= new_w[i]; j--) {
            dp[j] = max(dp[j], dp[j - new_w[i]] + new_v[i]);
        }
    }
    return dp[W];
}

fn multiple_knapsack_binary(w_cap: usize, weights: &[usize], values: &[i32], counts: &[usize]) -> i32 {
    let mut new_w = Vec::new();
    let mut new_v = Vec::new();
    for i in 0..weights.len() {
        let mut remain = counts[i];
        let mut k = 1;
        while k <= remain {
            new_w.push(k * weights[i]);
            new_v.push(k as i32 * values[i]);
            remain -= k;
            k *= 2;
        }
        if remain > 0 {
            new_w.push(remain * weights[i]);
            new_v.push(remain as i32 * values[i]);
        }
    }

    let mut dp = vec![0; w_cap + 1];
    for i in 0..new_w.len() {
        for j in (new_w[i]..=w_cap).rev() {
            dp[j] = dp[j].max(dp[j - new_w[i]] + new_v[i]);
        }
    }
    dp[w_cap]
}

单调队列优化

核心思想

二进制拆分将复杂度降到了 \(O(W \cdot \sum \log k[i])\)，但仍非最优。单调队列优化可以做到 \(O(n \cdot W)\)。

对于第 i 个物品（重量 w、价值 v、数量 k），将容量 j 按对 w 的余数 r = j mod w 分组。在同一组内，令 j = r + p·w，则：

\[ dp[j] = \max_{0 \le t \le k} \{ dp[r + (p-t) \cdot w] + t \cdot v \} \]

令 g(q) = dp[r + q·w] - q·v，则转移变为：

\[ dp[r + p \cdot w] = \max_{p-k \le q \le p} \{ g(q) \} + p \cdot v \]

这是一个滑动窗口最大值问题，窗口大小为 k+1，使用单调队列即可在 \(O(1)\) 内完成每次转移。

时间复杂度：\(O(n \cdot W)\)
空间复杂度：\(O(W)\)

PythonC++Rust

from collections import deque

def multiple_knapsack_monotone(W: int, weights: list, values: list, counts: list) -> int:
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        w, v, k = weights[i], values[i], counts[i]
        if w == 0:
            # 重量为 0 时直接加满
            for j in range(W + 1):
                dp[j] += k * v
            continue
        for r in range(w):  # 按余数分组
            q = deque()  # 存储下标 p，单调递减队列（按 g(p) 值）
            max_p = (W - r) // w
            for p in range(max_p + 1):
                val = dp[r + p * w] - p * v
                # 移除窗口外元素
                while q and q[0] < p - k:
                    q.popleft()
                # 维护单调性
                while q and dp[r + q[-1] * w] - q[-1] * v <= val:
                    q.pop()
                q.append(p)
                dp[r + p * w] = dp[r + q[0] * w] - q[0] * v + p * v
    return dp[W]

int multiple_knapsack_monotone(int W, vector<int>& weights, vector<int>& values, vector<int>& counts) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < weights.size(); i++) {
        int w = weights[i], v = values[i], k = counts[i];
        if (w == 0) {
            for (int j = 0; j <= W; j++) dp[j] += k * v;
            continue;
        }
        for (int r = 0; r < w; r++) {
            deque<int> q;
            int max_p = (W - r) / w;
            for (int p = 0; p <= max_p; p++) {
                int val = dp[r + p * w] - p * v;
                while (!q.empty() && q.front() < p - k) q.pop_front();
                while (!q.empty() && dp[r + q.back() * w] - q.back() * v <= val) q.pop_back();
                q.push_back(p);
                dp[r + p * w] = dp[r + q.front() * w] - q.front() * v + p * v;
            }
        }
    }
    return dp[W];
}

use std::collections::VecDeque;

fn multiple_knapsack_monotone(w_cap: usize, weights: &[usize], values: &[i64], counts: &[usize]) -> i64 {
    let mut dp = vec![0i64; w_cap + 1];
    for i in 0..weights.len() {
        let (w, v, k) = (weights[i], values[i], counts[i]);
        if w == 0 {
            for j in 0..=w_cap {
                dp[j] += k as i64 * v;
            }
            continue;
        }
        for r in 0..w {
            let mut q: VecDeque<usize> = VecDeque::new();
            let max_p = (w_cap - r) / w;
            for p in 0..=max_p {
                let val = dp[r + p * w] - p as i64 * v;
                while let Some(&front) = q.front() {
                    if front + k < p { q.pop_front(); } else { break; }
                }
                while let Some(&back) = q.back() {
                    if dp[r + back * w] - back as i64 * v <= val { q.pop_back(); } else { break; }
                }
                q.push_back(p);
                let best = *q.front().unwrap();
                dp[r + p * w] = dp[r + best * w] - best as i64 * v + p as i64 * v;
            }
        }
    }
    dp[w_cap]
}

三种方法对比

方法	时间复杂度	空间复杂度	适用场景
朴素枚举	\(O(n \cdot W \cdot \sum k[i])\)	\(O(W)\)	`k[i]` 很小时足够
二进制拆分	\(O(W \cdot \sum \log k[i])\)	\(O(W + \sum \log k[i])\)	通用，实现简单，竞赛首选
单调队列	\(O(n \cdot W)\)	\(O(W)\)	最优复杂度，`k[i]` 较大时优势明显