背包DP

参考：

1 0-1 背包问题

背包问题是一个非常好的动态规划入门题目，是动态规划中最常见的问题形式。其具有很多变种，例如 0-1 背包问题、完全背包问题、多重背包问题等。

在本节中，我们先来求解最常见的 0-1 背包问题。

Question

(给定 $n$ 个物品，第 $i$ 个物品的重量^[经典背包问题里物品重量为整数] 为 $w g t [i - 1]$ 、价值为 $v a l [i - 1]$ ，和一个容量为 $c a p$ 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。)

观察图 14-17 ，由于物品编号 $i$ 从 $1$ 开始计数，数组索引从 $0$ 开始计数，因此物品 $i$ 对应重量 $w g t [i - 1]$ 和价值 $v a l [i - 1]$ 。

0-1 背包的示例数据

图 14-17 0-1 背包的示例数据

我们可以将 0-1 背包问题看作一个由 $n$ 轮决策组成的过程，对于每个物体都有不放入和放入两种决策，因此该问题满足决策树模型。

该问题的目标是求解“在限定背包容量下能放入物品的最大价值”，因此较大概率是一个动态规划问题。

第一步：思考每轮的决策，定义状态，从而得到 $d p$ 表

对于每个物品来说，不放入背包，背包容量不变；放入背包，背包容量减小。由此可得状态定义：当前物品编号 $i$ 和背包容量 $c$ ，记为 $[i, c]$ 。

状态 $[i, c]$ 对应的子问题为： 前 $i$ 个物品在容量为 $c$ 的背包中的最大价值 ，记为 $d p [i, c]$ 。

待求解的是 $d p [n, c a p]$ ，因此需要一个尺寸为 $(n + 1) \times (c a p + 1)$ 的二维 $d p$ 表。

第二步：找出最优子结构，进而推导出状态转移方程

当我们做出物品 $i$ 的决策后，剩余的是前 $i - 1$ 个物品决策的子问题，可分为以下两种情况。

不放入物品 $i$ ：背包容量不变，状态变化为 $[i - 1, c]$ 。
放入物品 $i$ ：背包容量减少 $w g t [i - 1]$ ，价值增加 $v a l [i - 1]$ ，状态变化为 $[i - 1, c - w g t [i - 1]]$ 。

上述分析向我们揭示了本题的最优子结构： 最大价值 $d p [i, c]$ 等于不放入物品 $i$ 和放入物品 $i$ 两种方案中价值更大的那一个 。由此可推导出状态转移方程：

d p [i, c] = ma x (d p [i - 1, c], d p [i - 1, c - w g t [i - 1]] + v a l [i - 1])

需要注意的是，若当前物品重量 $w g t [i - 1]$ 超出剩余背包容量 $c$ ，则只能选择不放入背包。

第三步：确定边界条件和状态转移顺序

当无物品或背包容量为 $0$ 时最大价值为 $0$ ，即首列 $d p [i, 0]$ 和首行 $d p [0, c]$ 都等于 $0$ 。

当前状态 $[i, c]$ 从上方的状态 $[i - 1, c]$ 和左上方的状态 $[i - 1, c - w g t [i - 1]]$ 转移而来，因此通过两层循环正序遍历整个 $d p$ 表即可。

根据以上分析，我们接下来按顺序实现暴力搜索、记忆化搜索、动态规划解法。

1.1 方法一: 暴力搜索

搜索代码包含以下要素。

递归参数 ：状态 $[i, c]$ 。
返回值 ：子问题的解 $d p [i, c]$ 。
终止条件 ：当物品编号越界 $i = 0$ 或背包剩余容量为 $0$ 时，终止递归并返回价值 $0$ 。
剪枝：若当前物品重量超出背包剩余容量，则只能选择不放入背包。

/* 0-1 背包：暴力搜索 */
int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return max(no, yes);
}

如图 14-18 所示，由于每个物品都会产生不选和选两条搜索分支，因此时间复杂度为 $O (2^{n})$ 。

这个方法的空间复杂度是多少？

这个 knapsack01_dfs 方法的空间复杂度是 O(n)，其中 n 是物品的数量。

原因分析

该方法是递归实现，每次递归调用时，参数 i 减小 1，直到为 0 结束。

递归调用的最大深度是 n（即物品数量），因为每次最多只减少一个物品。

每次递归会在调用栈上分配一个新的栈帧，所以空间复杂度与递归深度成正比。

需要注意的点

如果你没有使用记忆化（比如 unordered_map 或二维数组缓存结果），空间复杂度不会因为重复子问题而增加，只和递归深度有关。

如果加上记忆化（动态规划），空间复杂度会变成 O(n * c)，其中 c 是背包容量。

观察递归树，容易发现其中存在重叠子问题，例如 $d p [1, 10]$ 等。而当物品较多、背包容量较大，尤其是相同重量的物品较多时，重叠子问题的数量将会大幅增多。

0-1 背包问题的暴力搜索递归树

图 14-18 0-1 背包问题的暴力搜索递归树

1.2 方法二: 记忆化搜索

为了保证重叠子问题只被计算一次，我们借助记忆列表 mem 来记录子问题的解，其中 mem[i][c] 对应 $d p [i, c]$ 。

引入记忆化之后， 时间复杂度取决于子问题数量 ，也就是 $O (n \times c a p)$ 。实现代码如下：

/* 0-1 背包：记忆化搜索 */
int knapsackDFSMem(vector<int> &wgt, vector<int> &val, vector<vector<int>> &mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有记录，则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
    int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(no, yes);
    return mem[i][c];
}

Note

此方法的空间复杂度为 $O (n \times c a p)$ ，其中 $n$ 为物品数量， $c a p$ 为背包容量。

Note

这里的方法用二维数组 mem 来存储子问题的解，包括后面的两种方法，个人认为在 cap 非常大的情况下不适用，效果可能还不一定有方法一来的有效。

图 14-19 展示了在记忆化搜索中被剪掉的搜索分支。

0-1 背包问题的记忆化搜索递归树

图 14-19 0-1 背包问题的记忆化搜索递归树

1.3 方法三: 动态规划

动态规划实质上就是在状态转移中填充 $d p$ 表的过程，代码如下所示：

/* 0-1 背包：动态规划 */
int knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

如图 14-20 所示，时间复杂度和空间复杂度都由数组 dp 大小决定，即 $O (n \times c a p)$ 。

0-1 背包问题的动态规划过程

knapsack_dp_step

图 14-20 0-1 背包问题的动态规划过程

1.4 空间优化

由于每个状态都只与其上一行的状态有关，因此我们可以使用两个数组滚动前进，将空间复杂度从 $O (n * c)$ 降至 $O (c)$ 。

进一步思考，我们能否仅用一个数组实现空间优化呢？观察可知，每个状态都是由正上方或左上方的格子转移过来的。假设只有一个数组，当开始遍历第 $i$ 行时，该数组存储的仍然是第 $i - 1$ 行的状态。

如果采取正序遍历，那么遍历到 $d p [i, j]$ 时，左上方 $d p [i - 1, 1]$ ~ $d p [i - 1, j - 1]$ 值可能已经被覆盖，此时就无法得到正确的状态转移结果。
如果采取倒序遍历，则不会发生覆盖问题，状态转移可以正确进行。

图 14-21 展示了在单个数组下从第 $i = 1$ 行转换至第 $i = 2$ 行的过程。请思考正序遍历和倒序遍历的区别。

0-1 背包的空间优化后的动态规划过程

knapsack_dp_comp_step

图 14-21 0-1 背包的空间优化后的动态规划过程

在代码实现中，我们仅需将数组 dp 的第一维 $i$ 直接删除，并且把内循环更改为倒序遍历即可：

/** 01背包：动态规划(空间进优化版,最优解法) TC: O(nc) SC: O(c) */
int knapsack01_dp(vector<int>& wgt, vector<int>& val, int c) {
    int n = wgt.size();
    vector<int> dp(c + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = c; j >= wgt[i - 1]; j--) {
            dp[j] = max(dp[j], dp[j - wgt[i - 1]] + val[i - 1]);
        }
    }
    return dp[c];
}

2 完全背包问题

Question

(给定 $n$ 个物品，第 $i$ 个物品的重量为 $w g t [i - 1]$ 、价值为 $v a l [i - 1]$ ，和一个容量为 $c a p$ 的背包。 每个物品可以重复选取 ，问在限定背包容量下能放入物品的最大价值。示例如图 14-22 所示。)

完全背包问题的示例数据

图 14-22 完全背包问题的示例数据

2.1 动态规划思路

完全背包问题和 0-1 背包问题非常相似， 区别仅在于不限制物品的选择次数 。

在 0-1 背包问题中，每种物品只有一个，因此将物品 $i$ 放入背包后，只能从前 $i - 1$ 个物品中选择。
在完全背包问题中，每种物品的数量是无限的，因此将物品 $i$ 放入背包后， 仍可以从前 $i$ 个物品中选择 。

在完全背包问题的规定下，状态 $[i, c]$ 的变化分为两种情况。

不放入物品 $i$ ：与 0-1 背包问题相同，转移至 $[i - 1, c]$ 。
放入物品 $i$ ：与 0-1 背包问题不同，转移至 $[i, c - w g t [i - 1]]$ 。

从而状态转移方程变为：

d p [i, c] = ma x (d p [i - 1, c], d p [i, c - w g t [i - 1]] + v a l [i - 1])

2.2 代码实现

对比两道题目的代码，状态转移中有一处从 $i - 1$ 变为 $i$ ，其余完全一致：

/* 完全背包：动态规划 */
int unboundedKnapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

2.3 空间优化

由于当前状态是从左边和上边的状态转移而来的， 因此空间优化后应该对 $d p$ 表中的每一行进行正序遍历 。

这个遍历顺序与 0-1 背包正好相反。请借助图 14-23 来理解两者的区别。

完全背包问题在空间优化后的动态规划过程

unbounded_knapsack_dp_comp_step

图 14-23 完全背包问题在空间优化后的动态规划过程

代码实现比较简单，仅需将数组 dp 的第一维删除：

/** 完全背包 TC: O(nc) SC: O(c) */
int knapsack_dp(vector<int>& wgt, vector<int>& val, int c) {
    int n = wgt.size();
    vector<int> dp(c + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = wgt[i - 1]; j <= c; j++) {
            dp[j] = max(dp[j], dp[j - wgt[i - 1]] + val[i - 1]);
        }
    }
    return dp[c];
}

3 多重背包

Question

你有 $n$ 个物品，每个物品重量为 $w_{i}$ ，价值为 $v_{i}$ ，数量为 $k_{i}$ 。你有一个承重上限为 $W$ 的背包，现在要求你在不超过重量上限的情况下选取价值和尽可能大的物品放入背包。求最大价值。

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 $k_{i}$ 个，而非一个。

多重背包问题在实际中很常见：

资源分配问题（每种资源有数量限制）
投资组合优化（每种投资项目有份额限制）
物流配送（每种货物有库存限制）

多重背包问题比 0-1 背包更接近实际应用场景，因为现实中物品通常不是只有一个，而是有一定的数量限制。

例题: 4. 多重背包问题 I

3.1 朴素解法

一个很朴素的想法就是：把「每种物品选 $k_{i}$ 次」等价转换为「有 $k_{i}$ 个相同的物品，每个物品选一次」。这样就转换成了一个 0-1 背包模型，套用上文所述的方法就可已解决。状态转移方程如下：

f_{i, j} = k = 0 max k_{i} (f_{i - 1, j - k \times w_{i}} + v_{i} \times k)

时间复杂度 $O (W \sum_{i = 1}^{n} k_{i})$ 。

3.1.1 方法一: 构建新物品数组

/* 朴素解法1: 构建新物品数组，转0-1背包 */
int knapsack_multi_naive1(const vector<int>& w, const vector<int>& v, const vector<int>& k, int W) {
    vector<int> new_w;
    vector<int> new_v;
    for (int i = 0; i < w.size(); ++i) {
        for (int j = 0; j < k[i]; ++j) {
            new_w.push_back(w[i]);
            new_v.push_back(v[i]);
        }
    }
    // 0-1背包问题
    int N = new_w.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < N; ++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];
}

3.1.2 方法二: 直接枚举

/* 朴素解法2：加物品循环 */
int knapsack_multi_naive2(const vector<int>& w, const vector<int>& v, const vector<int>& k, int W) {
    int N = w.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = W; j >= w[i]; --j) {
            for (int m = 1; m <= k[i] && m * w[i] <= j; ++m) {
                dp[j] = max(dp[j], dp[j - m * w[i]] + m * v[i]);
            }
        }
    }
    return dp[W];
}

3.1.3 方法三: 0-1 背包 + 完全背包

前面我们是把所有物品全部转化成 01 背包来做，但是我们想一想，是不是有的物品可以转化成完全背包呢？

完全背包问题是每件物品全部是无限件。我们这里有无限拿的物品吗？我们可以想想，总的背包体积就是 V ，是已经确定了的，如果我们有一种物品占用体积为 v，共有 s 件，但 sv >=V，不就代表着我们连 s 件物品都不可能拿完背包就已经塞不下了吗？所以这种情况我们可以转换成完全背包来做，只需要加一个判断就可以了。

为什么要转换成完全背包？我们看上面转化成 01 背包是需要枚举一下拿多少件的，而转化为完全背包是不需要枚举多少件的，可以拿我们就拿，所以在时间上会有一些优化。

/* 朴素解法3: 0-1背包 + 完全背包 */
int knapsack_multi_naive3(const vector<int>& w, const vector<int>& v, const vector<int>& k, int W) {
    int N = w.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < N; ++i) {
        if (k[i] * w[i] >= W) { // 物品足够多，可以认为可以无限拿 -> 完全背包
            for (int j = w[i]; j <= W; ++j) {
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        } else { // 物品不够多 -> 0-1背包处理
            for (int j = W; j >= w[i]; --j) {
                // 物品循环
                for (int m = 1; m <= k[i] && m * w[i] <= j; ++m) {
                    dp[j] = max(dp[j], dp[j - m * w[i]] + m * v[i]);
                }
            }
        }
    }
    return dp[W];
}

Note

这里其实已经有混合背包的影子了。

3.2 二进制分组优化

例题: 5. 多重背包问题 II

考虑优化。我们仍考虑把多重背包转化成 0-1 背包模型来求解。

显然，复杂度中的 $O (nW)$ 部分无法再优化了，我们只能从 $O (\sum k_{i})$ 处入手。

我们可以通过「二进制分组」的方式使拆分方式更加优美。

具体地说就是令 $A_{i, j} (j \in [0, ⌊ lo g_{2} (k_{i} + 1)⌋ - 1])$ 分别表示由 $2^{j}$ 个单个物品「捆绑」而成的大物品。特殊地，若 $k_{i} + 1$ 不是 $2$ 的整数次幂，则需要在最后添加一个由 $k_{i} - 2^{⌊ l o g_{2} (k_{i} + 1)⌋ - 1}$ 个单个物品「捆绑」而成的大物品用于补足。

举几个例子：

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

显然，通过上述拆分方式，可以表示任意 $\leq k_{i}$ 个物品的等效选择方式。将每种物品按照上述方式拆分后，使用 0-1 背包的方法解决即可。

时间复杂度 $O (W \sum_{i = 1}^{n} lo g_{2} k_{i})$

Note

有些求解场景不可修改输入数组，会多个新建数组的步骤，在 $\sum k_{i}$ 较小的情况下二进制优化方法的优势可能不太明显。

更详细的解释见多重背包问题中二进制优化的动机。

完整代码：

/* 二进制优化 */
int knapsack_multi_binary(const vector<int>& w, const vector<int>& v, const vector<int>& k, int W) {
    // 构建二进制分组数组
    vector<int> new_w, new_v;
    new_w.reserve(w.size() * 20); // 这里的20根据k的取值范围调整
    new_v.reserve(v.size() * 20);
    for (int i = 0; i < (int)w.size(); i++) {
        int b = 1, c = k[i];
        while (c > b) {
            new_w.push_back(b * w[i]);
            new_v.push_back(b * v[i]);
            c -= b;
            b *= 2;
        }
        new_w.push_back(c * w[i]);
        new_v.push_back(c * v[i]);
    }
 
    // 0-1b背包
    int N = new_w.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < N; ++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];
}

3.3 单调队列优化

见单调队列与单调栈优化。

例题: 6. 多重背包问题 III

3.3.1 正序遍历

/* 单调队列优化 */
int knapsack_multi_monotonic_queue(const vector<int>& w, const vector<int>& v, const vector<int>& k, int W) {
    int N = w.size();
    vector<vector<int>> dp(2, vector<int>(W + 1, 0));
    int pre = 0, cur = 1;
    for (int i = 0; i < N; ++i) {
        // 按 y 分组
        for (int y = 0; y < w[i]; ++y) {
            // 朴素解法的转移方程为：
            //		f_{i,j} = max(f_{i-1,j-k*w[i]}+k*v[i]), k=0,1,...,k[i]
            // 令：
            //		g_{x,y} = f_{i,x*w[i]+y}, g'_{x,y} = f_{i-1,x*w[i]+y}, 其中 0<=y<w[i]
            // 则转移方程可表示为：
            //		g_{x,y} = f_{i,x*w[i]+y} = max(f_{i-1,x*w[i]+y-k*w[i]}+k*v[i]), k=0,1,...,k[i]
            //				= max(f_{i-1,(x-k)*w[i]+y}+k*v[i]), k=0,1,...,k[i]
            // 				= max(g'_{x-k,y}+k*v[i]), k=0,1,...,k[i]
            // 令：
            //		G_{x,y} = g'_{x,y} - x*v[i]
            // 则：
            //		g_{x,y} = max(g'_{x-k,y}+k*v[i]), k=0,1,...,k[i]
            // 				= max(G{x-k,y}+(x-k)*v[i]+k*v[i]), k=0,1,...,k[i]
            // 				= max(G{x-k,y}+x*v[i]), k=0,1,...,k[i]
            // 				= max(G{x-k,y}) + x*v[i] , k=0,1,...,k[i]
            // 其中 max 部分可以通过单调队列遍历，使复杂度由 O(k[i]) 降为 O(1)
            // 因此可以对序列: G_{x,y}, x=0,1,2,...,W/w[i] 用大小为 k[i] 的单调递减队列遍历
            // 本质上遍历的是：
            // 		G_{x,y} = f_{i-1,x*w[i]+y} - x*v[i] , x=0,1,2,...,W/w[i]
            // 则队列的左边界为 x-k[i], 右边界为 x, 小于左边界的值应从队首弹出
            // 设队首为 x_front, 则:
            // 		G_{x_front,y} = max(G{x-k,y}), k=0,1,...,k[i]
            // 所以要更新的状态量为：
            // 		f_{i,x*w[i]+y} = g_{x,y} = max(G_{x,y}, G_{x-1,y},...,G_{x-k[i],y}) + x*v[i]
            // 					   = max(G{x-k,y}) + x*v[i] , k=0,1,...,k[i]
            // 					   = f_{i-1,x_front*w[i]+y} - x_front*v[i] + x*v[i]
			deque<int> qu;
            for (int x = 0; x * w[i] + y <= W; ++x) {
                // 弹出不在范围的元素
                while (!qu.empty() && qu.front() < x - k[i]) {
                    qu.pop_front();
                }
                // 保持单调递减
                while (!qu.empty() && dp[pre][qu.back() * w[i] + y] - qu.back() * v[i] < dp[pre][x * w[i] + y] - x * v[i]) {
                    qu.pop_back();
                }
                qu.push_back(x);
                // 此时队首为最大
                dp[cur][x * w[i] + y] = dp[pre][qu.front() * w[i] + y] - qu.front() * v[i] + x * v[i];
            }
        }
        swap(pre, cur); // 注意: 因为这里从小到大遍历，不能像0-1背包那样从大到小，所以必须申请副本存i-1状态的，不然会被影响
 
        // 至此,经过 y,x 循环更新完 f_{i,0} ~ f_{i,W}
    }
    return dp[pre][W];
}

3.3.2 倒序遍历

/* 单调队列优化(倒序遍历版) */
int knapsack_multi_monotonic_queue_reverse(const vector<int>& w, const vector<int>& v, const vector<int>& k, int W) {
    int N = w.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < N; ++i) {
        // 按 y 分组
        for (int y = 0; y < w[i]; ++y) {
            deque<int> qu;
            int r = (W - y) / w[i]; // 最大 x 值
            // 对于 x, 需要的窗口是 [x-k[i], x]，因此预先插入 [r-k[i]+1, r] 的元素
            for (int x = r; x > r - k[i] && x >= 0; --x) {
                // 此处元素肯定未出边界,因此不用验证
                // 保持单调递减, 新值放队首
                while (!qu.empty() && dp[qu.front() * w[i] + y] - qu.front() * v[i] < dp[x * w[i] + y] - x * v[i]) {
                    qu.pop_front();
                }
                qu.push_front(x);
            }
            for (int x = r; x >= 0; --x) {
                // 弹出不在范围的元素
                while (!qu.empty() && qu.back() > x) {
                    qu.pop_back();
                }
                // 对应要插入的新值为 x - k[i], 如果 x - k[i] < 0, 则不需要插入
                int new_x = x - k[i];
                if (new_x >= 0) {
                    // 保持单调递减, 新值放队首
                    while (!qu.empty() && dp[qu.front() * w[i] + y] - qu.front() * v[i] < dp[new_x * w[i] + y] - new_x * v[i]) {
                        qu.pop_front();
                    }
                    qu.push_front(new_x);
                }
                // 此时队尾为最大
                dp[x * w[i] + y] = dp[qu.back() * w[i] + y] - qu.back() * v[i] + x * v[i];
            }
        }
    }
    return dp[W];
}

3.4 所有方法运行结果

w: [15, 8, 12, 6, 25, 18, 9, 14, 22, 11, 7, 16, 20, 13, 10, 19, 24, 17, 21, 26]
v: [24, 15, 20, 12, 35, 28, 18, 25, 40, 22, 14, 30, 38, 26, 19, 33, 45, 31, 42, 50]
k: [1500, 2800, 1200, 3500, 800, 1100, 3200, 1600, 700, 2200, 4000, 1300, 900, 2500, 3800, 1000, 600, 1800, 1400, 750]
W: 150000
---
朴素解法1: 300000 (耗时: 3606.92 毫秒)
朴素解法2: 300000 (耗时: 4876.23 毫秒)
朴素解法3: 300000 (耗时: 4774.52 毫秒)
二进制优化: 300000 (耗时: 21.7392 毫秒)
单调队列优化: 300000 (耗时: 27.394 毫秒)
单调队列优化(倒序遍历): 300000 (耗时: 25.8748 毫秒)

Note

这里单调队列的方法比二进制还慢些, 说明常数项影响还比较大当问题规模更大时, 单调队列的优势会更明显。

习题：「Luogu P1776」宝物筛选_NOI 导刊 2010 提高（02）

4 混合背包

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 $k$ 次。

这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了。下面给出伪代码：

核心代码

for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}

例题

有 $n$ 种樱花树和长度为 $T$ 的时间，有的樱花树只能看一遍，有的樱花树最多看 $A i$ 遍，有的樱花树可以看无数遍。每棵樱花树都有一个美学值 $C i$ ，求在 $T$ 的时间内看哪些樱花树能使美学值最高。

5 二维背包

「Luogu P1855」榨取 kkksc03

有 $n$ 个任务需要完成，完成第 $i$ 个任务需要花费 $t i$ 分钟，产生 $c i$ 元的开支。

现在有 $T$ 分钟时间， $W$ 元钱来处理这些任务，求最多能完成多少任务。

这道题是很明显的 0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间），只需在状态中增加一维存放第二种价值即可。

这时候就要注意，再开一维存放物品编号就不合适了，因为容易 MLE。

核心代码

for (int k = 1; k <= n; k++)
  for (int i = m; i >= mi; i--)    // 对经费进行一层枚举
    for (int j = t; j >= ti; j--)  // 对时间进行一层枚举
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);

例题: 8. 二维费用的背包问题

6 双背包

与常规背包问题类似, 只不过背包有两个。为每个背包定义一个状态即可, 见相关问题:

两个货轮

Caution

注意和多重背包问题区分开来，双背包或多背包问题中的每个背包都是独立的，而多重背包问题是物品数量是有限的。

7 分组背包

Note

更多见分组背包

「Luogu P1757」通天之分组背包

有 $n$ 件物品和一个大小为 $m$ 的背包，第 $i$ 个物品的价值为 $w i$ ，体积为 $v i$ 。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。

这种题怎么想呢？其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

再说一说如何进行存储。我们可以将 $t k, i$ 表示第 $k$ 组的第 $i$ 件物品的编号是多少，再用 $c n t k$ 表示第 $k$ 组物品有多少个。

核心代码

for (int k = 1; k <= ts; k++)          // 循环每一组
  for (int i = m; i >= 0; i--)         // 循环背包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      if (i >= w[t[k][j]])             // 背包容量充足
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移

这里要注意： 一定不能搞错循环顺序 ，这样才能保证正确性。

例题

9. 分组背包问题

8 有依赖的背包

「Luogu P1064」金明的预算方案

金明有 $n$ 元钱，想要买 $m$ 个物品，第 $i$ 件物品的价格为 $v i$ ，重要度为 $p i$ 。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。

目标是让所有购买的物品的 $v i \times p i$ 之和最大。

8.1 转分组背包

考虑分类讨论。对于一个主件和它的若干附件，有以下几种可能：只买主件，买主件 + 某些附件。因为这几种可能性只能选一种，所以可以将这看成分组背包。

例题

购买 Steam 上的游戏

8.2 树上背包

如果是多叉树的集合，则要先算子节点的集合，最后算父节点的集合。

例题

树上背包（二） : 多叉树

9 泛化物品背包 - 背包问题的统一框架

这种背包，没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包容量为 $V$ 的背包问题中，当分配给它的费用为 $v i$ 时，能得到的价值就是 $h (v i)$ 。这时，将固定的价值换成函数的引用即可。

Note

其实所有类型的背包都可归纳到泛化背包的框架中来

泛化背包可以理解为：对于每个 ” 决策单元 “（可以是单个物品、一组物品、或某种状态），在给定的约束条件下，选择最优的决策方案。

9.1 可以归纳的背包问题

01 背包 - 每个物品选 0 或 1 次
- 决策单元：单个物品
- 决策选项：选或不选
完全背包 - 每个物品可选无限次
- 决策单元：单个物品
- 决策选项：选 0 次、1 次、2 次…
多重背包 - 每个物品有数量限制
- 决策单元：单个物品
- 决策选项：选 0 次、1 次…最多 k 次
分组背包 - 每组最多选一个物品
- 决策单元：一组物品
- 决策选项：从组内选一个或不选
二维背包 - 两个约束条件（体积 + 重量）
- 决策单元：单个物品
- 约束维度：从 1 维扩展到多维
双背包/多背包 - 多个背包可选
- 决策单元：单个物品
- 决策选项：放入背包 1、背包 2…或不放
依赖背包 - 物品之间有依赖关系
- 决策单元：物品及其依赖链
- 约束条件：满足依赖关系
树形背包 - 树形结构的依赖关系
- 决策单元：树节点及其子树
- 状态定义：dp[节点][容量]

9.2 统一的 DP 状态转移框架

// 对于每个决策单元 i
for (决策单元 i) {
    // 对于每个容量状态 j（倒序/正序取决于问题类型）
    for (容量 j) {
        // 枚举所有可能的决策
        for (决策 k) {
            // 状态转移
            dp[j] = optimize(dp[j], dp[j - cost[i][k]] + value[i][k]);
        }
    }
}

9.3 不太容易归纳的特殊情况

背包问题的方案数/路径记录 - 需要额外维护状态
带有复杂约束的背包（如互斥、顺序约束）- 可能需要状态压缩 DP
连续背包（分数背包）- 贪心算法更优，不需要 DP

9.4 核心思想

所有背包问题的本质都是：

状态定义：dp[约束条件] = 最优值
决策过程：如何从一个状态转移到另一个状态
优化目标：最大化/最小化某个目标函数

所以可以说，泛化背包提供了一个统一的思维框架，通过调整以下要素可以解决大部分背包问题：

决策单元的定义
状态维度的设计
决策空间的枚举方式
状态转移的方向（正序/倒序）

这就是为什么理解了 01 背包后，其他背包问题都可以看作是在这个基础上的变形和扩展。

10 杂项

10.1 小优化

根据贪心原理，当费用相同时，只需保留价值最高的；当价值一定时，只需保留费用最低的；当有两件物品 $i, j$ 且 $i$ 的价值大于 $j$ 的价值并且 $i$ 的费用小于 $j$ 的费用时，只需保留 $i$ 。

10.2 背包问题变种

10.2.1 输出方案

输出方案其实就是记录下来背包中的某一个状态是怎么推出来的。我们可以用 $g i, v$ 表示第 $i$ 件物品占用空间为 $v$ 的时候是否选择了此物品。然后在转移时记录是选用了哪一种策略（选或不选）。输出时的伪代码：

int v = V;  // 记录当前的存储空间
 
// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件) {
  if (g[i][v]) {
    选了第 i 项物品;
    v -= 第 i 项物品的重量;
  } else {
    未选第 i 项物品;
  }
}

例题: 12. 背包问题求具体方案

10.2.2 求方案数

对于给定的一个背包容量、物品费用、其他关系等的问题，求装到一定容量的方案总数。

这种问题就是把求最大值换成求和即可。

例如 0-1 背包问题的转移方程就变成了：

dp_{i} = \sum (dp_{i}, dp_{i - c_{i}})

初始条件： $dp_{0} = 1$

因为当容量为 $0$ 时也有一个方案，即什么都不装。

10.2.3 求最优方案总数

要求最优方案总数，我们要对 0-1 背包里的 $dp$ 数组的定义稍作修改，DP 状态 $f_{i, j}$ 为在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包「正好装满」所能达到的最大总价值。

这样修改之后，每一种 DP 状态都可以用一个 $g_{i, j}$ 来表示方案数。

$f_{i, j}$ 表示只考虑前 $i$ 个物品时背包体积「正好」是 $j$ 时的最大价值。

$g_{i, j}$ 表示只考虑前 $i$ 个物品时背包体积「正好」是 $j$ 时的方案数。

转移方程：

如果 $f_{i, j} = f_{i - 1, j}$ 且 $f_{i, j} \neq = f_{i - 1, j - v} + w$ 说明我们此时不选择把物品放入背包更优，方案数由 $g_{i - 1, j}$ 转移过来，

如果 $f_{i, j} \neq = f_{i - 1, j}$ 且 $f_{i, j} = f_{i - 1, j - v} + w$ 说明我们此时选择把物品放入背包更优，方案数由 $g_{i - 1, j - v}$ 转移过来，

如果 $f_{i, j} = f_{i - 1, j}$ 且 $f_{i, j} = f_{i - 1, j - v} + w$ 说明放入或不放入都能取得最优解，方案数由 $g_{i - 1, j}$ 和 $g_{i - 1, j - v}$ 转移过来。

初始条件：

memset(f, 0x3f3f, sizeof(f));  // 避免没有装满而进行了转移
f[0] = 0;
g[0] = 1;  // 什么都不装是一种方案

因为背包体积最大值有可能装不满，所以最优解不一定是 $f_{m}$ 。

最后我们通过找到最优解的价值，把 $g_{j}$ 数组里取到最优解的所有方案数相加即可。

for (int i = 0; i < N; i++) {
  for (int j = V; j >= v[i]; j--) {
    int tmp = std::max(dp[j], dp[j - v[i]] + w[i]);
    int c = 0;
    if (tmp == dp[j]) c += cnt[j];                       // 如果从dp[j]转移
    if (tmp == dp[j - v[i]] + w[i]) c += cnt[j - v[i]];  // 如果从dp[j-v[i]]转移
    dp[j] = tmp;
    cnt[j] = c;
  }
}
int max = 0;  // 寻找最优解
for (int i = 0; i <= V; i++) {
  max = std::max(max, dp[i]);
}
int res = 0;
for (int i = 0; i <= V; i++) {
  if (dp[i] == max) {
    res += cnt[i];  // 求和最优解方案数
  }
}

例题:

11. 背包问题求方案数输出 最优选法的方案数

10.2.4 背包的第 k 优解

普通的 0-1 背包是要求最优解，在普通的背包 DP 方法上稍作改动，增加一维用于记录当前状态下的前 k 优解，即可得到求 0-1 背包第 $k$ 优解的算法。具体来讲： $d p_{i, j, k}$ 记录了前 $i$ 个物品中，选择的物品总体积为 $j$ 时，能够得到的第 $k$ 大的价值和。这个状态可以理解为将普通 0-1 背包只用记录一个数据的 $d p_{i, j}$ 扩展为记录一个有序的优解序列。转移时，普通背包最优解的求法是 $d p_{i, j} = max (d p_{i - 1, j}, d p_{i - 1, j - v_{i}} + w_{i})$ ，现在我们则是要合并 $d p_{i - 1, j}$ ， $d p_{i - 1, j - v_{i}} + w_{i}$ 这两个大小为 $k$ 的递减序列，并保留合并后前 $k$ 大的价值记在 $d p_{i, j}$ 里，这一步利用双指针法，复杂度是 $O (k)$ 的，整体时间复杂度为 $O (nmk)$ 。空间上，此方法与普通背包一样可以压缩掉第一维，复杂度是 $O (mk)$ 的。

例题 HDU 2639 Bone Collector II

求 0-1 背包的严格第 $k$ 优解。 $n \leq 100, v \leq 1000, k \leq 30$

实现

memset(dp, 0, sizeof(dp));
int i, j, p, x, y, z;
scanf("%d%d%d", &n, &m, &K);
for (i = 0; i < n; i++) scanf("%d", &w[i]);
for (i = 0; i < n; i++) scanf("%d", &c[i]);
for (i = 0; i < n; i++) {
  for (j = m; j >= c[i]; j--) {
    for (p = 1; p <= K; p++) {
      a[p] = dp[j - c[i]][p] + w[i];
      b[p] = dp[j][p];
    }
    a[p] = b[p] = -1;
    x = y = z = 1;
    while (z <= K && (a[x] != -1 || b[y] != -1)) {
      if (a[x] > b[y])
        dp[j][z] = a[x++];
      else
        dp[j][z] = b[y++];
      if (dp[j][z] != dp[j][z - 1]) z++;
    }
  }
}
printf("%d\n", dp[m][K]);

10.3 非 DP 背包问题

有些问题形似背包问题，但并不是 DP 问题

Explorer

背包DP

1 0-1 背包问题

1.1 方法一: 暴力搜索

原因分析

需要注意的点

1.2 方法二: 记忆化搜索

1.3 方法三: 动态规划

1.4 空间优化

2 完全背包问题

2.1 动态规划思路

2.2 代码实现

2.3 空间优化

3 多重背包

3.1 朴素解法

3.1.1 方法一: 构建新物品数组

3.1.2 方法二: 直接枚举

3.1.3 方法三: 0-1 背包 + 完全背包

3.2 二进制分组优化

3.3 单调队列优化

3.3.1 正序遍历

3.3.2 倒序遍历

3.4 所有方法运行结果

4 混合背包

5 二维背包

6 双背包

7 分组背包

8 有依赖的背包

8.1 转分组背包

8.2 树上背包

9 泛化物品背包 - 背包问题的统一框架

9.1 可以归纳的背包问题

9.2 统一的 DP 状态转移框架

9.3 不太容易归纳的特殊情况

9.4 核心思想

10 杂项

10.1 小优化

10.2 背包问题变种

10.2.1 输出方案

10.2.2 求方案数

10.2.3 求最优方案总数

10.2.4 背包的第 k 优解

10.3 非 DP 背包问题

10.3.1 浮点数背包

目录

Graph View

反向链接