【动态规划】背包问题详解_背包问题 动态规划
赞
踩
动态规划（Dynamic Pogramming，简称dp）是运筹学的一个分支，是求解决策过程最优化的数学方法。背包问题则是dp问题里很常见的一类。本篇文章来详解一下背包问题。
1、基础知识
动态规划的理解方式有很多种，这里讲述的是yxc老师的闫氏dp法，个人认为是最好的理解方式并且非常好用。
遇到dp问题，首先考虑状态表示，即如何（用什么、怎么样）把一个状态表示出来，区分两个不同状态的指标数量叫维度，我们要把相同的状态放入一个集合里面去，并且规定这个集合的属性（可能是最大值、最小值、元素数量等）。在此之后，我们要考虑状态计算，即如何把当前状态的集合计算出来。在这一步，我们一般采用划分集合的方式，即将一个大的集合划分为很多小的集合，这些小的集合可以计算出来，那么大的集合也就能计算出来了。一般要求是：划分集合时不重不漏。
听起来很抽象，确实是这样。dp问题需要不断做题积累经验，才能真正体会到其中的精髓。下面用背包问题来走一遍这个流程，方便理解。
背包问题是动态规划问题里的一种很常见题型，具体来说就是，给一个容量确定的背包，给一些体积确定、价值确定的物品，问怎样带才能带走价值最大的物品。好比说打游戏时，打怪掉落了很多物资，但是背包有限，就要想想带走什么才对自己最有用。我们用闫氏dp法来走一遍流程。
首先，考虑如何表示一个背包的状态：1.背包容量；2.放哪些物品。因此，背包问题集合的维度是二维的。具体表示方法不同的题目不同。因为问题需要，所以集合的属性自然就是价值的最大值。
然后就要考虑状态的计算了，即如何计算
f
(
i
,
j
)
f(i,j)
f(i,j)的值。这个过程我们采取划分集合的方式，不同的题目有不同的考虑方式，下面用一些例题来实战。
2、01背包
01背包具体是：一个物品只有选（1）或不选（0）两种状态，固称为01背包。首先看一下例题 acwing 01背包
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 v i v_i vi, w i w_i wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0< v i v_i vi, w i w_i wi≤1000
输入样例4 5
1 2
2 4
3 4
4 5输出样例：
8
我们可以用 f ( i , j ) f(i,j) f(i,j)来表示：只在前 i i i个物品里面选，且背包容量为 j j j。
划分集合时可以将只在前 i i i个物品里选划分为两个小集合：
- 所有选了 i i i的选法： f ( i − 1 , j − v i ) + w i f(i-1,j-v_i)+w_i f(i−1,j−vi)+wi；
- 所有不选 i i i的选法： f ( i − 1 , j ) f(i-1,j) f(i−1,j)。
这样就能不重不漏的把
f
(
i
,
j
)
f(i,j)
f(i,j)分为两个小的集合了。同时由于
f
(
i
,
j
)
f(i,j)
f(i,j)的属性是最大值，那么就可以表示为：
f
(
i
,
j
)
=
m
a
x
(
f
(
i
−
1
,
j
−
v
i
)
+
w
i
,
f
(
i
−
1
,
j
)
)
f(i,j)=max(f(i-1,j-v_i)+w_i, f(i-1,j))
f(i,j)=max(f(i−1,j−vi)+wi,f(i−1,j))
这样就得到了dp问题最重要的状态计算方程。
得到了这个，这个题就可以直接做出来了：
#include <iostream> using namespace std; const int N = 1010; int f[N][N]; int v[N], w[N]; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; //因为i等于0的时候f(i,j)一定是0（选0个物品），所以直接从1开始 for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) { f[i][j] = f[i - 1][j]; //只有装得下物品i时，才考虑选了i的选法 if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); } cout << f[n][m]; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
dp问题就是这样神奇，看似很难，其实只要得到状态计算方程，很简洁的代码就能通过。
接下来，还能对代码进行优化。注意到 f ( i , j ) = m a x ( f ( i − 1 , j − v i ) + w i , f ( i − 1 , j ) ) f(i,j)=max(f(i-1,j-v_i)+w_i, f(i-1,j)) f(i,j)=max(f(i−1,j−vi)+wi,f(i−1,j))，每个 i i i状态都是由 i − 1 i-1 i−1状态得到的，因此可以用滚动数组的方式来更新。意思是：一个二维数组，每行都是由上一行得到的，那么就可以优化为一个一维数组，每次用新的值覆盖当前值，也即相当于由上一行得到下一行。那么核心部分代码：
f[i][j] = f[i - 1][j];
- 1
就可以优化为：
f[j] = f[j];
- 1
恒等式可以省略；其次第二个核心代码：
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
- 1
可以优化为：
if (j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
- 1
而由于循环是递增的，所以直接从v[i]开始即可：
for (int i = 1; i <= n; i ++ )
for (int j = v[i]; j <= m; j ++ )
f[j] = max(f[j], f[j - v[i]] + w[i]);
- 1
- 2
- 3
但是这里有一个问题：注意到 f [ j − v [ i ] ] f[j-v[i]] f[j−v[i]]一定小于 f [ j ] f[j] f[j]，所以它一定会在 f [ j ] f[j] f[j]之前更新，那么更新 f [ j ] f[j] f[j]时，就相当于用本层的 f [ j − v [ i ] ] f[j-v[i]] f[j−v[i]]来更新，但计算公式要求用上一层的 f [ j − v [ i ] ] f[j-v[i]] f[j−v[i]]来更新，为解决这个问题，只需要把第二层循环逆向进行即可。这样能保证更新 f [ j ] f[j] f[j]时用到的是上一层的 f [ j − v [ i ] ] f[j-v[i]] f[j−v[i]]。
那么得到01背包问题的终极版代码：
#include <iostream> using namespace std; const int N = 1010; int f[N]; int v[N], w[N]; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i ++ ) for (int j = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m]; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
3、完全背包
完全背包就是给出一些物品，但是物品数量不限。例题 acwing完全背包
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 v i v_i vi, w i w_i wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0< v i v_i vi, w i w_i wi≤1000
输入样例4 5
1 2
2 4
3 4
4 5输出样例：
10
还可以用
f
(
i
,
j
)
f(i,j)
f(i,j)来表示：只在前
i
i
i个物品里面选，且背包容量为
j
j
j。
但是划分集合的时候，就和01背包略有不同了。因为物品是无限使用，所以划分为：
- 第 i i i件物品选了0个的选法： f ( i − 1 , j ) f(i-1,j) f(i−1,j)；
- 第 i i i件物品选了1个的选法： f ( i − 1 , j − v i ) + w i f(i-1,j-v_i)+w_i f(i−1,j−vi)+wi；
- 第
i
i
i件物品选了2个的选法：
f
(
i
−
1
,
j
−
2
v
i
)
+
2
w
i
f(i-1,j-2v_i)+2w_i
f(i−1,j−2vi)+2wi；
……
第 i i i件物品选了s个的选法： f ( i − 1 , j − s v i ) + s w i f(i-1,j-sv_i)+sw_i f(i−1,j−svi)+swi，（ s × v i ≤ j s×v_i≤j s×vi≤j）；
这样就能做到不重不漏地把
f
(
i
,
j
)
f(i,j)
f(i,j)划分为了
s
s
s个集合。所以可以得到状态计算方程：
f
(
i
,
j
)
=
m
a
x
(
f
(
i
−
1
,
j
−
k
v
i
)
+
k
w
i
)
，
(
k
=
0
,
1
,
2
,
…
,
s
)
f(i,j)=max(f(i-1,j-kv_i)+kw_i)，(k=0,1,2,…,s)
f(i,j)=max(f(i−1,j−kvi)+kwi)，(k=0,1,2,…,s)
那么题解就有了：
#include <iostream> using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N][N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) for (int k = 0; k * v[i] <= j; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); cout << f[n][m] << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
可以进行进一步优化。这里注意到一个神奇的事情：
也即，当
v
i
≥
j
v_i≥j
vi≥j时，有
f
(
i
,
j
)
=
f
(
i
,
j
−
v
i
)
+
w
i
f(i,j)=f(i,j-v_i)+w_i
f(i,j)=f(i,j−vi)+wi。
有了这个，就可以对完全背包进行优化了：
#include <iostream> using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N][N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) { f[i][j] = f[i - 1][j]; if (v[i] <= j) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
这样少了一重循环，时间复杂度就变成O(mn)了。
再和01背包一样进行一维优化，得到最终版代码：
#include <iostream> using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i ++ ) //注意这里的区别是j递增，和01背包相反，一定要想清为什么 for (int j = v[i]; j <= m; j ++ ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
j j j是递增的原因：公式中 f ( i , j ) f(i,j) f(i,j)的更新就是用本层的 f ( i , j − v i ) f(i,j-v_i) f(i,j−vi)。
4、多重背包问题
完全背包就是给出一些物品，但是物品数量有限。例题 acwing多重背包
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 s i s_i si 件，每件体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 v i v_i vi, w i w_i wi, s i s_i si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0< v i v_i vi, w i w_i wi, s i s_i si≤2000
输入样例4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例：
10
用
f
(
i
,
j
)
f(i,j)
f(i,j)来表示：只在前
i
i
i个物品里面选，且背包容量为
j
j
j。
划分集合的时候，因为物品是有限使用，所以划分为：
- 第 i i i件物品选了0个的选法： f ( i − 1 , j ) f(i-1,j) f(i−1,j)；
- 第 i i i件物品选了1个的选法： f ( i − 1 , j − v i ) + w i f(i-1,j-v_i)+w_i f(i−1,j−vi)+wi；
- 第
i
i
i件物品选了2个的选法：
f
(
i
−
1
,
j
−
2
v
i
)
+
2
w
i
f(i-1,j-2v_i)+2w_i
f(i−1,j−2vi)+2wi；
……
第 i i i件物品选了 s i s_i si个的选法： f ( i − 1 , j − s v i ) + s w i f(i-1,j-sv_i)+sw_i f(i−1,j−svi)+swi；
这样就能做到不重不漏地把
f
(
i
,
j
)
f(i,j)
f(i,j)划分为了
s
s
s个集合。所以可以得到状态计算方程：
f
(
i
,
j
)
=
m
a
x
(
f
(
i
−
1
,
j
−
k
v
i
)
+
k
w
i
)
，
(
k
=
0
,
1
,
2
,
…
)
f(i,j)=max(f(i-1,j-kv_i)+kw_i)，(k=0,1,2,…)
f(i,j)=max(f(i−1,j−kvi)+kwi)，(k=0,1,2,…)
注意这里的
k
v
i
kv_i
kvi一定是小于
j
j
j的。
那么就可以得到题解：
#include <iostream> using namespace std; const int N = 110; int f[N][N]; int v[N], w[N], s[N]; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i]; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) for (int k = 0; k * v[i] <= j && k <= s[i]; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); cout << f[n][m] << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
但是浅看一下时间复杂度，三重循环，最坏 1000 × 2000 × 2000 1000×2000×2000 1000×2000×2000，大约是四十亿，明显超时了（C++每秒大概运算一亿次），所以就要优化。这里的优化是一个技巧，叫二进制优化。
假设有1023个物品，那么进行分组：20,21,22,23,24,…,29。也即1,2,4,8,…,512。用这几个数，就能组合出0 ~ 1023中所有的数。那么原来的1024（0 ~ 1023）个数，就变成了10个数进行组合。假如物品数不是2n-1个，例如45，那么就分组：20,21,22,23,24,45-24。也就是1,2,4,8,16,14。用这几个数就能组合出0 ~ 45所有的数了。
把分的每个组想成一个物品，其实就转化成了01背包问题，因为每组只能是选或不选。因此用01背包的代码即可解决，重点是分组。这时看一下时间复杂度，也就是 V × N × l o g s i V×N×logs_i V×N×logsi，差不多 1000 × 2000 × l o g 2000 1000×2000×log2000 1000×2000×log2000，大概两千万，可以接受。那么给出优化的多重背包问题：
#include <iostream> using namespace std; //物品总数大概是N(组数)*log si(每组里的小组数) //1000*log2000≈11000 const int N = 11010, M = 2010; int f[N]; int v[N], w[N]; int n, m; int main() { cin >> n >> m; //分组 int cnt = 0; for (int i = 1; i <= n; i ++ ) { int a, b, s; cin >> a >> b >> s; int k = 1; while (k <= s) { cnt ++ ; v[cnt] = k * a; w[cnt] = k * b; s -= k; k *= 2; } if (s > 0) { cnt ++ ; v[cnt] = s * a; w[cnt] = s * b; } } //分组后的物品数 n = cnt; for (int i = 1; i <= n; i ++ ) for (int j = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
5、分组背包问题
分组背包问题简单来说就是每组只能选一个物品或不选。
例题 acwing分组背包
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v i j v_{ij} vij，价值是 w i j w_{ij} wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 S i S_i Si，表示第 i 个物品组的物品数量；
每组数据接下来有 S i S_i Si 行，每行有两个整数 v i j v_{ij} vij, w i j w_{ij} wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0< S i S_i Si≤100
0< v i j v_{ij} vij, w i j w_{ij} wij≤100
输入样例3 5
2
1 2
2 4
1
3 4
1
4 5输出样例：
8
用
f
(
i
,
j
)
f(i,j)
f(i,j)来表示：只在前
i
i
i组里面选，且背包容量为
j
j
j。
划分集合的时候，因为物品是有限使用，所以划分为：
- 第 i i i组物品不选的选法： f ( i − 1 , j ) f(i-1,j) f(i−1,j)；
- 第 i i i组物品选第1个的选法： f ( i − 1 , j − v i 1 ) + w i 1 f(i-1,j-v_{i1})+w_{i1} f(i−1,j−vi1)+wi1；
- 第
i
i
i组物品选第2个的选法：
f
(
i
−
1
,
j
−
v
i
2
)
+
w
i
2
f(i-1,j-v_{i2})+w_{i2}
f(i−1,j−vi2)+wi2；
……
第 i i i组物品选第 s i s_i si个的选法： f ( i − 1 , j − v i s i ) + w i s i f(i-1,j-v_{is_i})+w_{is_i} f(i−1,j−visi)+wisi；
由于思路较为简单，所以直接给出一维优化后的代码：
#include <iostream> using namespace std; const int N = 110; int v[N][N], w[N][N], s[N]; int f[N]; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) { cin >> s[i]; for (int j = 1; j <= s[i]; j ++ ) cin >> v[i][j] >> w[i][j]; } for (int i = 1; i <= n; i ++ ) for (int j = m; j >= 1; j -- ) for (int k = 0; k <= s[i]; k ++ ) if (v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); cout << f[m] << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
