1. 题目

1.1 题目描述

有件物品和一个容量为的背包。「每件物品只能使用一次」。 第件物品的体积是，价值是。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

1.2 经典例题

洛谷P1048 [NOIP2005 普及组] 采药

2. 思路

2.1 基本思路

这是最基础的背包问题，特点是：「每种物品仅有一件，可以选择取或不取」。 考虑如何将问题转化成规模更小的子问题。对于第件物品，在最终方案中要么不取、要么取，于是我们可以对这两种情况进行分类讨论，转化为子问题：

• 如果不取第件物品，那么相当于只有前件物品、背包大小相同的子问题

• 如果取了第件物品，那么相当于只有前件物品（件物品已经经过了选择）、背包大小减去的子问题，在它的答案上再加上的价值（取了第件物品贡献的价值）。

在这两种情况中取价值更高的，作为答案。

2.2 状态转移方程

设表示使用编号为的物品，背包容量为时的最大价值，有转移方程：

2.3 例子

为了加深对状态转移方程的理解，我们来看下图的一个例子，每个格子代表一个状态，代表初始状态，蓝色的格子代表已经求得的状态，灰色的格子代表非法状态，红色的格子代表当前正在进行转移的状态，图中的第行代表了前个物品对应容量的最优值，第个物品的体积为，价值为，则有状态转移如下：

2.4 代码

for (int i = 1; i <= n; i++) {  // 遍历物品
    for (int j = 0; j <= W; j++) {  // 遍历背包容量
        if (j < w[i]) dp[i][j] = dp[i-1][j];
        else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
    }
}


3. 优化空间复杂度

我们发现以上方法的状态数是的，整个求解过程的时间和空间复杂度均为，其中时间复杂度已经不能再优化了，但是空间复杂度还是可以优化的。

3.1 滚动数组

我们观察刚才的代码：每个在转移时只用到了，即上一行的数据。也就是说，比更小的再也不会被用到。如果把看成一张二维的表格，那么只有两行的格子是 “活跃” 的。基于这一思想，我们可以只保存这两行。

3.2 代码

int pre = 0, cur = 1;  // pre:前一行  cur:当前行
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        if (j < w[i]) dp[cur][j] = dp[pre][j];
        else dp[cur][j] = max(dp[pre][j], dp[pre][j-w[i]] + v[i])
    }
    swap(pre, cur);  // 每一轮结束 当前行变成前一行, 交换, 每次只用两行的空间
}


3.3 一维数组

我们继续刚才的思路：把看成一张二维的表格，那么每个格子在转移时，只会用到上一行中在它左侧的格子。如果我们调整一下转移的顺序，每一行从右往左进行更新（从大到小），那么 「“活跃”」 的格子就正好只有「上一行的左半部分以及这一行的右半部分」。（即除白色格子以外的格子）

那么实际上我们只需要保存这些 “活跃” 格子的状态就可以了，我们可以得到一维的状态转移方程：

3.4 代码

for (int i = 1; i <= n; i++) {  // 遍历物品
    for (int j = W; j >= w[i]; j--) {  // 遍历背包容量
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}


3.5 例子

我们通过下面这个例子来深入理解下，为什么降维之后，遍历背包容量（内层循环）要「逆序遍历」。 假定目前背包容量为，有以下三个物品：

求将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

「我们先来看内层循环」「从小到大遍历（顺序遍历）的情况」：

背包基本要求是「每件物品只能使用一次」，我们从使用第一件物品的时候，就可以发现如果内层循环从小到大遍历，那么这件物品会被多次使用。
比如的状态一定来自，而的状态来自于，这时候我们发现体积为的第一件物品被用了两次：

「接下来我们来看下内层循环」「从大到小遍历（逆序遍历）的情况」：

上面「逆序遍历」的是不是就实现了每件物品只使用一次的要求，其实「顺序遍历」 每件物品可以被反复使用，这个就是我们后面要讲的完全背包。

4. 经典题型

4.1 最大值问题

「题目链接」：洛谷P1048 [NOIP2005 普及组] 采药
「题意」：有件物品和一个容量为的背包。「每件物品只能使用一次。」第件物品的体积是，价值是。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
「题解」：模板题，见上文

4.2 最小值问题

「题目链接」：洛谷P1049 [NOIP2001 普及组] 装箱问题
「题意」：有一个箱子容量为，同时有个物品，每个物品有一个体积。
现在从个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。
「题解」：本题可以认为每个物品的价值就是体积，: 在的箱子容量下能够装入的最大总体积。 题目要求最少剩余空间，那么我们最后答案就是。 对于这种最小值问题，我们转化下思路，用总值减去求得的最大值，即是最小值。
「扩展题目」：有件物品，第件物品价值为，现在要把这些物品分成两堆，期望两堆的价值之差最小，求最小价值差。（原理本质来说是一样的，我们先用求出所有物品价值之和，然后求出，即尽可能接近总价值一半的情况，最后答案就是）。

4.3 存在性问题

「题目链接」：洛谷P1877 [HAOI2012] 音量调节
「题意」：给定首歌和刚开始的音量，每首歌开始前能够改变的音量是(当前音量调高或者调低)，音量不能小于且不能大于。求首歌演唱完之后，最大音量是多少。
「题解」：存在性问题本质来说就是在背包基础上，用表示能够达到这个状态，表示不能够达到这个状态。
在本题中表示能否达到这个音量，一开始我们把数组初始化成，表示所有音量都无法达到，然后把题目中给定的初始音量标记成，即。

在每首歌开始前，我们可以在当前音量的基础上增加或减少，那么我们是不是就可以去检测一下或是否在之前达到过，如果达到过我们就能在之前的状态基础上，增加或者减少，达到这个音量。
「细节问题」：本题无法用一维数组优化空间复杂度的形式（但是滚动数组还是可以的），问题在于我们内层循环「逆序遍历」的过程中，会影响到，使得该次改变执行了多次（即背包中该件物品反复使用），和上文讲到的内层循环「顺序遍历」，会影响到，使得该件物品反复使用，原理一样。
「练习题目」：洛谷P8742 [蓝桥杯 2021 省A] 砝码称重

4.4 二维费用问题

「题目链接」：洛谷P1794 装备运输
「题意」：有件物品和一个可容纳体积、承载重量的背包。「每件物品只能使用一次。」第件物品的体积是，重量是，价值是。求解将哪些物品装入背包，可使得这些物品的总体积不超过背包的可容纳体积、总重量不超过背包的可承载重量，且总价值最大。
「题解」：经典背包的费用只有体积，二维费用问题是在原来问题的基础上多加了一维费用，那对应的我们只需要给状态也多加一维就好了。为了保证每件物品只使用一次，对于体积和重量的这两维，我们都采用逆序的循环。对应的状态转移方程：
「代码」：

for (int i = 1; i <= n; i++)
for (int j = V; j >= v[i]; j--)
for (int k = G; k >= g[i]; k--)
dp[j][k] = max(dp[j][k], dp[j - v[i]][k - g[i]] + t[i]);


「练习题目」：洛谷P1507 NASA的食物计划

4.5 方案数问题

「题目链接」：AcWing 背包问题求方案数
「题意」：有件物品和一个容量为的背包。「每件物品只能使用一次。」第件物品的体积是，价值是。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出「最优选法的方案数」。注意答案可能很大，请输出答案模的结果。
「题解」：对于求解方案数的问题，主要在于转移方程的时候不再是、，或者像存在性问题进行标记，而是说我们需要把之前状态的方案数加到当前状态上，即，具体我们看下这个例题。
本题求在最优选法情况下的方案数。那么我们在原来求最优选法背包的基础上，可以再定义一个数组，表示在的背包大小下最优选法的方案数。那么数组会受到数组（或者说最优选法）的影响。有以下两种情况：

• 当，即在背包大小为，在使用第个物品的时候出现了一个新的最优值，那么显然我们需要更新下。同时我们要让，因为这时候出现了新的最优选法，原来的就没用了，我们拿当前转移过来的方案数即赋值。

• 当，即在背包大小为，在使用第个物品的时候出现了一个一样的最优值情况，那么我们这时候只需要给加上这种情况的方案，即

普通的求方案数问题只需要转移就可以了，比如练习题目中的 「小A点菜」，把之前所有能够转移到当前状态的前置状态的方案数都加上。但是加上了最优之类的条件，我们就需要考虑当前状态的转移是「更优的情况」还是「一样优的情况，」根据不同情况对方案计数进行更改。
同样的思想在图论的最短路（松弛操作）、拓扑排序之类算法问题中也经常出现。
「细节问题」：本题需要考虑把先全部初始化成，因为背包什么都不装也是一种方案。
「代码」：

for (int i = 1; i <= N; i++)
    for (int j = V; j >= v[i]; j--) {
        if (dp[j] < dp[j - v[i]] + w[i]) {
            dp[j] = dp[j - v[i]] + w[i];
            cnt[j] = cnt[j - v[i]] % mod;
        }
        else if (dp[j] == dp[j - v[i]] + w[i]) {
            cnt[j] = (cnt[j] + cnt[j - v[i]]) % mod;
        }
    }


「练习题目」：洛谷P1164 小A点菜

4.6 输出具体方案问题

「题目链接」：AcWing背包问题求具体方案
「题意」：有件物品和一个容量为的背包。「每件物品只能使用一次。」第件物品的体积是，价值是。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出「字典序最小的方案」。
「题解」：输出具体方案本质来说就是输出转移路径。假设最优解是，那么我们判断第个物品是否选择，实际上就是看是从哪个状态转移过来的：

• 如果，即不选第个物品。

• 如果，那么是选了这个物品，得到最优解。

「细节问题」：题目中要输出字典序最小的方案，我们物品得逆序遍历，因为从顺序遍历时，如果序号和序号的最大价值都是，那么最后记录的最大值对应的序号就是，后面的会给前面的覆盖掉，我们实际想要的是序号。
「代码」：

for (int i = N; i >= 1; i--) {
 for (int j = 1; j <= W; j++) {
  if (j >= w[i]) dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
  else dp[i][j] = dp[i+1][j];
 }
}

for (int i = 1; i <= N; i++) {
 if (W >= w[i] && dp[i][W] == dp[i+1][W-w[i]] + v[i]) {
  ans.push_back(i);
  W -= w[i];
 }
}


「扩展题目（大容量背包）」：有件物品和一个容量为的背包。「每件物品只能使用一次。」第件物品的体积是。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，求最大总体积是多少？具体方案是怎么样的？
（）「题解」：对于这种大容量背包，很明显开二维会炸空间。我们需要给它优化一下，给它降下维。有一种方式是可以用二进制bitset优化（这个不细说了，有兴趣的可以自己研究下）。我这里介绍下类似搜索中记录路径的方式，我们可以用去记录下在这个背包大小情况用了这个物品。最后倒序去遍历检测一下第物品是否需要被选（和上面小容量那题一样），并且是否记录在这个里。

for (int i = 1; i <= n; i++) {
    for (int j = W; j >= w[i]; j--) {
        if (dp[j-w[i]] + w[i] > dp[j]) {
            dp[j] = dp[j-w[i]] + w[i];
            path[j] = i;
        }
    }
}


for (int i = n; i >= 1; i--) {
    if (W >= w[i]&& dp[W] == dp[W-w[i]] + w[i] && path[W] == i) {
        ans.push_back(i);
        W -= w[i];
    }
}