背包问题及其优化
详细总结了01背包问题、完全背包问题、多重背包问题、分组背包问题以及混合背包问题的DP解法及其优化。
01背包问题
问题描述
01背包问题的描述如下:
有$N$件物品和一个容量是$V$的背包。
每件物品只能使用一次。第$i$件物品的体积是$v_i$,价值是 $w_i$。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。
输入格式:
第一行两个整数$N$,$V$,用空格隔开,分别表示物品数量和背包容积。
接下来有$N$行,每行两个整数$v_i$,$w_i$,用空格隔开,分别表示第$i$件物品的体积和价值。
输出格式:
输出一个整数,表示最大价值。
数据范围:
输入样例:
1
2
3
4
5 4 5
1 2
2 4
3 4
4 5输出样例:
1 8
问题分析
画出思维导图如下:
状态转移方程为,
代码实现
1 |
|
- 时间复杂度:$O(NV)$
- 空间复杂度:$O(NV)$
代码优化
优化一
观察到每次迭代,第$i$层都会将第$i-1$层覆盖,考虑使用滚动数组进行实现,减小存储空间的使用:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
const int N = 1010, M = 1010;
int v[N], w[N];
int f[M];
int main()
{
int n, m;
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[i - 1][j - v[i]]使用的是上一层的值,故此处应该从大到小更新,防止将上一层的值覆盖
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d", f[m]);
return 0;
}
- 时间复杂度:$O(NV)$
- 空间复杂度:$O(V)$
优化二
在优化一的基础上,可以一边输入一边计算,减少使用的存储空间:
1 |
|
- 时间复杂度:$O(NV)$
- 空间复杂度:$O(V)$
完全背包问题
问题描述
完全背包问题的描述如下:
有$N$种物品和一个容量是$V$的背包。
每种物品都有无限个可用。第$i$种物品的体积是$v_i$,价值是 $w_i$。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。
输入格式:
第一行两个整数$N$,$V$,用空格隔开,分别表示物品数量和背包容积。
接下来有$N$行,每行两个整数$v_i$,$w_i$,用空格隔开,分别表示第$i$件物品的体积和价值。
输出格式:
输出一个整数,表示最大价值。
数据范围:
输入样例:
1
2
3
4
5 4 5
1 2
2 4
3 4
4 5输出样例:
1 10
问题分析
画出思维导图如下:
代码实现
1 |
|
当$v_i$都为1时,最坏情况下时间复杂度为:$O(NVv^2)$。
代码优化
时间优化
观察到,
即$f(i, j-v_i)+w_i$与$f(i,j)$第二项开始的项相等。因此有,
优化后的代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
const int N = 1010;
int f[N][N], v[N], w[N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d%d", &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 (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
printf("%d", f[n][m]);
return 0;
}
- 时间复杂度:$O(NV)$
- 空间复杂度:$O(NV)$
空间优化
优化一
与01背包类似,减小一维数据:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N];
int main()
{
int n, m;
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 = v[i]; j <= m; j ++) // 由于f[i][j - v[i]]使用的是当前层的值,故此处应该从小到大更新,防止使用上一层的值
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d", f[m]);
return 0;
}
时间复杂度:$O(NV)$
空间复杂度:$O(V)$
优化后的代码与01背包的区别在于,完全背包的第二层循环是从小到大更新,而01背包为从大到小更新。
优化二
在优化一的基础上,边输入边计算,减小代码量与存储空间。
1 |
|
时间复杂度:$O(NV)$
空间复杂度:$O(V)$
多重背包问题
问题描述
多重背包问题的描述如下:
有$N$件物品和一个容量是$V$的背包。
第$i$种物品最多有$s_i$件,每件体积是$v_i$,价值是$w_i$。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。
输入格式:
第一行两个整数$N$,$V$,用空格隔开,分别表示物品种数和背包容积。
接下来有$N$行,每行两个整数$v_i$,$w_i$,$s_i$,用空格隔开,分别表示第$i$件物品的体积、价值和数量。
输出格式:
输出一个整数,表示最大价值。
数据范围一(无需优化):数据范围二(需要二进制优化):
输入样例:
1
2
3
4
5 4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例:
1 10
问题分析
多重背包问题与完全背包问题分析过程类似,思维导图如下:
状态转移方程为:
代码实现
1 |
|
- 当$s$都为$N$,且$v_i$都为1时,最坏时间复杂度:$O(NV^2)$
- 空间复杂度:$O(NV)$
代码优化
优化一
当$N$和$V$,以及$v_i,w_i,s_i$较大时,上述代码时间复杂度较高,会造成超时(在C++中,每秒大约计算$10^8$次),因此考虑对其进行优化。
类似的,由完全背包问题可以得到,
观察得到该式子比原状态转移方程多一项,即$f(i - 1, j - (s_i+1)v_i) + s_iw_i)$,因此不能使用优化完全背包的方法来优化多重背包问题,只能另辟蹊径。
使用二进制优化,将每种物品进行打包,然后使用01背包的方法进行解决。例如, 若某种物品有200件,将其分别打包成1, 2, 4, 8, 16, 32, 64, 73共8件,由于1~200之间的每个数都可以用这8件打包的物品数量凑出,将每一件打包的物品视作01背包问题中的一类物品,即可使用01背包进行解决。代码如下:
1 |
|
- 时间复杂度为:$O(NV)$
- 空间复杂度为:$O(V)$
优化二
在优化一的基础上,边输入边计算,减小代码量和存储空间。
1 |
|
- 时间复杂度为:$O(NV)$
- 空间复杂度为:$O(V)$
分组背包问题
问题描述
分组背包问题的描述如下:
有$N$件物品和一个容量是$V$的背包。
每组物品有若干个,同一组内的物品最多只能选一个。每件物品的体积是$v_{ij}$,价值是 $w_{ij}$,其中$i$是组号,$j$是组内编号。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。
输入格式:
第一行有两个整数 $N$,$V$,用空格隔开,分别表示物品组数和背包容量。
接下来有$N$组数据:
- 每组数据第一行有一个整数 $S_i$,表示第$i$个物品组的物品数量;
- 每组数据接下来有$S_i$行,每行有两个整数$v_{ij}$,$w_{ij}$,用空格隔开,分别表示第$i$个物品组的第$j$个物品的体积和价值;
输出格式:
输出一个整数,表示最大价值。
数据范围:
输入样例:
1
2
3
4
5
6
7
8 3 5
2
1 2
2 4
1
3 4
1
4 5输出样例:
1 8
问题分析
画出思维导图如下:
状态转移方程为:
代码实现
1 |
|
- 时间复杂度为:$O(NVS)$
- 空间复杂度为:$O(NV)$或$O(NS)$
代码优化
与01背包问题优化一类似,利用滚动数组减小一组存储空间。
1 |
|
- 时间复杂度为:$O(NVS)$
- 空间复杂度为:$O(NS)$
混合背包问题
问题描述
混合背包问题的描述如下:
有$N$种物品和一个容量是$V$的背包。
物品一共有三类:
- 第一类物品只能用1次(01背包);
- 第二类物品可以用无限次(完全背包);
- 第三类物品最多只能用$s_i$次(多重背包);
每种体积是$v_i$,价值是$w_i$。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。
输入格式
第一行两个整数,$N$, $V$,用空格隔开,分别表示物品种数和背包容积。
接下来有$N$行,每行三个整数$v_i$,$w_i$,$s_i$,用空格隔开,分别表示第$i$种物品的体积、价值和数量。
- $s_i$=−1表示第$i$种物品只能用1次;
- $s_i$=0表示第$i$种物品可以用无限次;
- $s_i$>0表示第$i$种物品可以使用$s_i$次;
输出格式
输出一个整数,表示最大价值。
数据范围
输入样例
1
2
3
4
5 4 5
1 2 -1
2 4 1
3 4 0
4 5 2输出样例:
1 8
问题分析
对每种不同类型的物品,计算时使用不同的状态转移方程即可。注意到,01背包问题其实是多重背包问题的一种特殊情况,因此可以将它们合并进行处理。
代码实现
1 |
|
- 最坏时间复杂度为:$O(NVS)$
- 空间复杂度为:$O(V)$