1 01 背包
1.1 题目描述
有
N
N
N 件物品和一个容量为
V
V
V 的背包。放入第
i
i
i 件物品的体积为
v
i
v_i
vi ，能够获得的价值为
w
i
w_i
wi 。求解将哪些物品放入背包可以使背包内物品价值总量最大，只需求出最大价值。
数据输入格式
第一行输入两个整数，
N
,
V
N,V
N,V，用空格隔开分别表示物品的种类和背包的容积；
接下来有 N 行数据，每一行有两个整数
v
i
和
w
i
v_i和w_i
vi和wi ，分别表示第
i
i
i 件物品的体积和价值。
输出格式
输出一个整数，表示背包可以容纳物品的最大价值。
数据范围
0
<
N
,
V
<
=
1000
0 < N,V <= 1000
0<N,V<=1000
0
<
v
i
,
w
i
<
=
1000
0 < v_i,w_i <= 1000
0<vi,wi<=1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8
解释
从物品中取出第二件和第三件物品放入背包，背包内的总价值最大为 8 。
1.2 基本思路
这是最基础的背包问题，其特点是：可以被选择的每种物品只有一件，可以选择放与不放。该特点也是01背包问题的关键，并且以后看到题目有这样的描述，那该题多半就是 01背包问题。
需要记录
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 这样一个状态值，
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示在前
i
i
i 种物品中随意挑选物品放在背包中，使背包内物品的总体积不能超过
j
j
j ，此时背包可以容纳的最大价值。题目要求的是面对这
N
N
N 种物品，我们可以随便挑选物品放在背包里，计算不超过背包可容纳体积时我们可以获得的最大价值。因此返回值就是
d
p
[
N
]
[
V
]
dp[N][V]
dp[N][V]。
状态转移方程为：
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
v
i
]
)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v_i])
dp[i][j]=max(dp[i−1][j],dp[i−1][j−vi])
这个方程非常重要，也是接下来其他类型的背包问题的基础。我们来分析一下，为了获得最大背包容量下的最大物品价值，我们有两种选择的方案，就是面对第
i
i
i 件物品的时候，我们有如下两种选择，而最最大价值就是其中的较大者。
-
选择1 放置第
i
i
i 件物品：此时就将该问题转化为 前
i
−
1
i-1
i−1 件物品放入容量为
j
−
v
i
j-v_i
j−vi 的背包 ，这时可以获得的最大价值就是
d
p
[
i
−
1
]
[
j
−
w
i
]
dp[i-1][j-w_i]
dp[i−1][j−wi] 再加上放入第
i
i
i 件物品的价值；
-
选择2 不放置第
i
i
i 件物品：此时就将该问题转化为 前
i
−
1
i-1
i−1 件物品放入容量为
j
j
j 的背包 求最大价值即
d
p
[
i
−
1
]
[
j
]
dp[i-1][j]
dp[i−1][j]；
伪代码：
d
p
[
0
]
[
0...
V
]
←
0
dp\left[ 0 \right] \left[ 0...V \right] \gets 0
dp[0][0...V]←0
f
o
r
i
←
1
t
o
N
for\ i\ \gets 1\ to\ N
for i ←1 to N
f
o
r
j
←
v
i
t
o
V
\quad \quad for\ j\gets v_i\ to\ V
for j←vi to V
d
p
[
i
]
[
j
]
←
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
v
i
]
+
w
i
)
\quad \quad \quad \quad dp\left[ i \right] \left[ j \right] \,\,\gets \max \left( dp\left[ i-1 \right] \left[ j \right] ,\,\,dp\left[ i-1 \right] \left[ j-v_i \right] +w_i \right)
dp[i][j]←max(dp[i−1][j],dp[i−1][j−vi]+wi)
1.3 空间上的优化
以上的求解方法时间复杂度和空间复杂度均是
O
(
N
V
)
O(NV)
O(NV)，其中时间复杂度已经不能够优化看了，而空间复杂度还有优化的空间，可以优化到
O
(
V
)
O(V)
O(V) 。
在上面的讲解思路中是有一个外层循环的
i
←
1...
N
i \leftarrow 1...N
i←1...N ，每次算出二维数组
d
p
[
i
,
0...
V
]
dp[i, 0...V]
dp[i,0...V] 的所有值。那么，如果只用一个数组
d
p
[
0...
V
]
dp[0...V]
dp[0...V] ，能不能保证计算完第
i
i
i 件物品的最大价值后
d
p
[
V
]
dp[V]
dp[V] 表示的就是我们定义的状态
d
p
[
i
]
[
V
]
dp[i][V]
dp[i][V] 呢？根据 1.2 基本思路 中的描述可以知道，面对第
i
i
i 件物品，
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 是由
d
p
[
i
−
1
]
dp[i-1]
dp[i−1] 和
d
p
[
i
−
1
]
[
j
−
v
i
]
dp[i-1][j-v_i]
dp[i−1][j−vi] 两个子问题递推来的，如果我们维护一个 背包最大容量长度的数组 表示的是面对前
i
−
1
i-1
i−1 种物品的最大价值，即计算面对第
i
i
i 件物品时的最大价值，
d
p
[
j
]
dp[j]
dp[j] 表示的是面对前
i
−
1
i-1
i−1 种物品背包容量是
j
j
j 的最大价值。
此时对于背包容量这一层该如何循环呢？这一层的循环以
j
←
V
t
o
0
j \leftarrow V\ to\ 0
j←V to 0 递减的顺序计算
d
p
[
j
]
dp[j]
dp[j] ，这样才能保证计算
d
p
[
j
]
dp[j]
dp[j] 时
d
p
[
j
−
v
i
]
dp[j-v_i]
dp[j−vi] 保存的是状态
d
p
[
i
−
1
]
[
j
−
v
i
]
dp[i-1][j-v_i]
dp[i−1][j−vi] 的值。
如果按照背包容量递增的顺序遍历会怎么样？面对第
i
i
i件物品
j
j
j 背包容量下的最大价值更新需要用到
d
p
[
i
−
1
,
0...
V
]
dp[i-1,\ 0...V]
dp[i−1, 0...V] 的数据。按照背包容量递增的顺序更新之后
d
p
[
j
]
dp[j]
dp[j] 表示的是
d
p
[
i
,
j
]
dp[i, j]
dp[i,j] ，而后面的
d
p
[
i
,
j
.
.
.
V
]
dp[i, j...V]
dp[i,j...V] 计算仍需要
d
p
[
i
−
1
,
.
.
.
]
dp[i-1, ...]
dp[i−1,...] 的状态信息，因此这样按照背包容量增加的顺序更新数组会出错。于是这一层的循环是以
j
←
V
t
o
0
j \leftarrow V\ to\ 0
j←V to 0 递减的顺序计算
d
p
[
j
]
dp[j]
dp[j] 的。
伪代码：
d
p
[
0...
V
]
←
0
dp\left[ 0...V \right] \gets 0
dp[0...V]←0
f
o
r
i
←
1
t
o
N
for\ i\ \gets 1\ to\ N
for i ←1 to N
f
o
r
j
←
V
t
o
v
i
\quad \quad for\ j\gets V\ to\ v_i
for j←V to vi
d
p
[
j
]
←
max
(
d
p
[
j
]
,
d
p
[
j
−
v
i
]
+
w
i
)
\quad \quad \quad \quad dp\left[ j \right] \,\,\gets \max \left( dp\left[ j \right] ,\,\,dp\left[ j-v_i \right] +w_i \right)
dp[j]←max(dp[j],dp[j−vi]+wi)
1.4 算法实现
#include <iostream>
using namespace std;
#define maxn 1010
int N, V; // 物品种类以及背包容量
int v[maxn], w[maxn]; // 物品的体积和价值数组
int dp[maxn][maxn]; // 背包内物品的最大价值，j体积下前i个物品最大价值
int get01BagMinVal() {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= V; ++j) {
// 当前背包容量可以装的下第i件物品，这时候有两种选择，取与不取
if (j >= v[i]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
}
当前背包容量装不下第i件物品
else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[N][V];
}
int main() {
cin >> N >> V;
for (int i = 1; i <= N; ++i) {
cin >> v[i] >> w[i];
}
return 0;
}
// 以上给出的是没有进行空间优化的 01 背包求解
1.5 递归版本
递归方法需要维护一个背包剩余容量的整型变量，每次选择了当前物品时，就是要计算利用下一件及其以后物品的最大价值与不选择当前物品时下一件及其以后物品的最大价值进行比较，选择较大的值作为最大价值。
int maxValue(vector<int>& w, vector<int>& v, int bag) {
return process(w, v, 0, bag);
}
// rest 表示背包剩下的空间
// idx 及其往右的货物可以选择，但是注意不能超过 rest 的空间
int process(int>& w, vector<int>& v, int idx, int rest) {
if (rest < 0) { // base case 1
return -1;
}
if (idx == w.size()) { // base case 2
return 0;
}
// 不选择 idx 位置的货物
int p1 = process(w, v, idx + 1, rest);
int p2 = -1;
// 选择 idx 位置的货物
int p2Next = process(w, v, idx + 1, rest - w[idx]);
if (p2Next != -1) {
p2 = v[idx] + p2Next;
}
return max(p1, p2);
}
1.6 按照递归修改的动态规划版本
有一种动态规划是可以根据递归方法修改得到的，递归里的 base case 对应的就是动态规划里的边界条件，而递归位置对应的就是动态规划里的转态转移。
int dpWay01(vector<int>& w, vector<int>& v, int bag) {
int n = w.size();
vector<vector<int>> dp(n+1, vector<int>(n+1));
// dp[n][...] 对应暴力递归中的 base case 2
for (int idx = n-1; idx >= 0; --idx) {
for (int rest = 0; rest <= bag; ++rest) {
dp[idx][rest] = dp[idx+1][rest];
if (rest >= w[idx]) {
dp[idx][rest] = max(dp[idx][rest], dp[idx + 1][rest - w[idx] + v[idx]);
}
}
}
return dp[0][bag];
}
1.7 总结
01 背包问题是背包类问题的最基础的部分，包含了背包问题的设计状态方程的基本思想，需要理解透彻。别的类型的题目往往可以转化为 01 背包的问题进行求解。一定要仔细体会状态转移方程的意义以及空间优化方法。
空间优化方法中一定要好好理解 背包容量的倒叙遍历，以上的相关描述的层次可能还有点不清晰，还需要对陈述继续进行打磨，最好可以用一些生动的图示进行描述说明该问题。
2 完全背包
2.1 题目描述
有
N
N
N 种物品和一个容量为
V
V
V 的背包，每种物品都有无限件可以用。放入第
i
i
i 件物品的体积为
v
i
v_i
vi ，能够获得的价值为
w
i
w_i
wi 。求解将哪些物品放入背包可以使背包内物品价值总量最大，只需求出最大价值。
2.2 基本思路
完全背包问题和 01背包问题很像的，主要区别在于：每种物品都有无限件。从每种物品的角度考虑，此时的策略已经不是取与不取的问题了，而是这种物品取0次、1次，…，
⌊
V
v
i
⌋
\lfloor \frac{V}{v_i} \rfloor
⌊viV⌋ 次。
如果仍然按照 01 背包求解的思路，令
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示前
i
i
i 件物品放入一个容量为
j
j
j 的背包的最大价值。按照完全背包的物品拿取策略有这样的状态转移方程：
d
p
[
i
]
[
j
]
=
max
{
d
p
[
i
−
1
]
[
j
−
k
v
i
]
+
k
w
i
∣
0
≤
k
v
i
≤
V
}
dp\left[ i \right] \left[ j \right] =\max \left\{ dp\left[ i-1 \right] \left[ j-kv_i \right] +kw_i|0\le kv_i\le V \right\}
dp[i][j]=max{dp[i−1][j−kvi]+kwi∣0≤kvi≤V}
按照这样求解的总的时间复杂度为
O
(
N
V
∑
V
v
i
)
O(NV\sum{\frac{V}{v_i}})
O(NV∑viV)，其中
∑
j
v
i
\sum{\frac{j}{v_i}}
∑vij 表示的是所有物品可以拿取的总次数。
根据上述状态方程描述有这样的代码：
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= V; ++j) {
for (int k = 0; k * v[i] <= j; ++k) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
2.3 优化一下
数学上的推导：
将基本思路中的状态转移方程按
k
k
k 可能的取值拆开有：
d
p
[
i
,
j
]
=
max
{
d
p
[
i
−
1
]
[
j
−
k
v
i
]
+
k
w
i
∣
0
≤
k
v
i
≤
V
}
=
max
{
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
v
i
]
+
w
i
,
d
p
[
i
−
1
]
[
j
−
2
v
i
]
+
2
w
i
,
.
.
.
,
d
p
[
i
−
1
]
[
j
−
k
v
i
]
+
k
w
i
}
dp\left[ i,\ j \right] =\max \left\{ dp\left[ i-1 \right] \left[ j-kv_i \right] +kw_i|0\le kv_i\le V \right\}= \\ \max \left\{ dp\left[ i-1 \right] \left[ j \right] ,\ dp\left[ i-1 \right] \left[ j-v_i \right] +w_i,\ dp\left[ i-1 \right] \left[ j-2v_i \right] +2w_i,\ ...,\ dp\left[ i-1 \right] \left[ j-kv_i \right] +kw_i \right\}
dp[i, j]=max{dp[i−1][j−kvi]+kwi∣0≤kvi≤V}=max{dp[i−1][j], dp[i−1][j−vi]+wi, dp[i−1][j−2vi]+2wi, ..., dp[i−1][j−kvi]+kwi}
将
j
=
j
−
v
i
j = j-v_i
j=j−vi 带入上式有：
d
p
[
i
,
j
−
v
i
]
+
w
i
=
max
{
d
p
[
i
−
1
]
[
j
−
v
i
−
m
v
i
]
+
k
w
i
∣
0
≤
(
m
+
1
)
v
i
≤
V
}
+
w
i
=
max
{
d
p
[
i
−
1
]
[
j
−
v
i
]
+
w
i
,
d
p
[
i
−
1
]
[
j
−
2
v
i
]
+
2
w
i
,
.
.
.
,
d
p
[
i
−
1
]
[
j
−
(
m
+
1
)
v
i
]
+
(
m
+
1
)
w
i
}
dp\left[ i,\ j-v_i \right] +w_i=\max \left\{ dp\left[ i-1 \right] \left[ j-v_i-mv_i \right] +kw_i|0\le \left( m+1 \right) v_i\le V \right\} +w_i=\\ \max \left\{ dp\left[ i-1 \right] \left[ j-v_i \right] +w_i,\ dp\left[ i-1 \right] \left[ j-2v_i \right] +2w_i,\ ...,\ dp\left[ i-1 \right] \left[ j-\left( m+1 \right) v_i \right] +\left( m+1 \right) w_i \right\}
dp[i, j−vi]+wi=max{dp[i−1][j−vi−mvi]+kwi∣0≤(m+1)vi≤V}+wi=max{dp[i−1][j−vi]+wi, dp[i−1][j−2vi]+2wi, ..., dp[i−1][j−(m+1)vi]+(m+1)wi}
以上两式中
k
=
=
m
+
1
k == m+1
k==m+1 的，表示的都是最大背包容量下可放置当前物品
i
i
i 的最大数量，即
k
=
=
m
+
1
=
=
⌊
V
v
i
⌋
k==m+1== \lfloor \frac{V}{v_i} \rfloor
k==m+1==⌊viV⌋ 。因此状态转移方程可以优化为：
d
p
[
i
]
[
j
]
=
max
{
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
v
i
]
+
w
i
}
dp\left[ i \right] \left[ j \right] =\max \left\{ dp\left[ i-1 \right] \left[ j \right] ,\ dp\left[ i-1 \right] \left[ j-v_i \right] +w_i \right\}
dp[i][j]=max{dp[i−1][j], dp[i−1][j−vi]+wi}
逻辑上的理解：
完全背包问题中的每种物品都可以无限使用的，在考虑 “再选一个第
i
i
i 件物品” 这种策略时，正需要一个可能已经选入第
i
i
i 种物品的子结果
d
p
[
i
]
[
j
−
v
i
]
dp[i][j-v_i]
dp[i][j−vi] ，所以这里内存循环的顺序也就是按照背包容量增加的顺序了。
通过以上分析，完全背包中的k循环可以被替换掉，于是有：
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= V; ++j) {
dp[i][j] = dp[i-1][j];
if (j >= v[i]) {
dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);
}
}
}
根据以上代码按照01背包的优化思路又可以使用一维动态数组进行如下优化，注意这里的内层循环是按照背包容量增加的顺序进行遍历。
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= V; ++j) {
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
}
}
伪代码：
d
p
[
0...
V
]
←
0
dp\left[ 0...V \right] \gets 0
dp[0...V]←0
f
o
r
i
←
1
t
o
N
for\ i\ \gets 1\ to\ N
for i ←1 to N
f
o
r
j
←
v
i
t
o
V
\quad \quad for\ j\gets v_i\ to\ V
for j←vi to V
d
p
[
j
]
←
max
(
d
p
[
j
]
,
d
p
[
j
−
v
i
]
+
w
i
)
\quad \quad \quad \quad dp\left[ j \right] \,\,\gets \max \left( dp\left[ j \right] ,\,\,dp\left[ j-v_i \right] +w_i \right)
dp[j]←max(dp[j],dp[j−vi]+wi)
算法复杂度：
时间复杂度：
O
(
N
V
)
O(NV)
O(NV)
空间复杂度：
O
(
V
)
O(V)
O(V)
2.4 代码实现
#include <iostream>
using namespace std;
#define maxn 1010
int N, V; // 物品种类以及背包容量
int v[maxn], w[maxn]; // 物品的体积和价值数组
int dp[maxn][maxn]; // 背包内物品的最大价值，j体积下前i个物品最大价值
int getCompleteBagMinVal() {
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= V; ++j) {
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
}
}
return dp[N][V];
}
int main() {
cin >> N >> V;
for (int i = 1; i <= N; ++i) {
cin >> v[i] >> w[i];
}
return 0;
}
2.5 总结
完全背包也是背包系列问题的基础问题。在这类问题中，第一个状态转移方程是比较容易理解的，优化后的状态转移方程相对不容易理解，并且内层循环容易受 01背包问题影响出错。
