基础背包问题

前言

背包问题一直是DP的经典模型,但是像我这样的菜鸡总是学不会 (再聪明一点) 所以综合之前的做题和听课,把自己的一点感悟记录下来。(大部分与背包九讲一致)

01背包

01背包是背包模型的基础,也是我DP入门的噩梦,那就从这个问题入手吧。

题目

N件物品和一个容量为V的背包,每件物品有一个体积为c,有一个价值为v。求解背包能装入最大的价值总和。

思路

状态表示: \(f[i][j]\) 表示前i件物品放入容量为j的背包所能获得的最大价值和

状态计算:

  • 状态转移方程: \(f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+v[i])\)
  • 初始状态: \(f[i][0]=0,f[0][j]=0\)
  • 边界条件: \(j<c[i]\) 时, \(f[i][j]=f[i-1][j]\)

代码

1
2
3
4
5
6
7
8
9
10
//初始状态由于定义全局变量默认为零故不用设置
for(int i = 1; i <= N; i ++)
{
for(int j = 0; j <= V; j++)
{
if(j < c[i]) f[i][j] = f[i - 1][j];//边界状态
else f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i]);//状态转移方程
}
}
cout << f[N][V] << endl;

空间复杂度优化

此处的优化方法主要是观察代码与状态转移方程得出的。注意到状态转移方程中 \(f[i][j]\) 仅由 \(f[i-1][j]\)\(f[i-1][j-c[i]]+w[i]\) 决定,故将第一维删去,得代码1:

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= N; i ++)
{
for(int j = 0; j <= V; j++)
{
if(j < c[i]) f[j] = f[j];//边界状态
else f[j] = max(f[j], f[j - c[i]] + w[i]);//状态转移方程
}
}
cout << f[V] << endl;

代码1存在两点问题

  • 问题1:边界状态为恒等式,删去
  • 问题2:考虑 \(i=I,j=J\) 时,此时由于内层循环是从小到大的顺序去更新,所以 \(f[J-c[I]]\)\(f[J]\) 之前被 \(c[I]\) 更新了,也就是说,此时的 \(f[J-c[I]]\) 等价于二维中的 \(f[I][J-c[I]]\) 而非 \(f[I-1][J-c[I]]\) ,所以内层循环应当从大至小,又考虑边界状态,终止条件就是 \(j>=c[i]\)

更改后得一维的01背包代码:

1
2
3
4
5
6
7
8
for(int i = 1; i <= N; i ++)
{
for(int j = V; j >= c[i]; j--)
{
f[j] = max(f[j], f[j - c[i]] + w[i]);//状态转移方程
}
}
cout << f[V] << endl;

装满问题

原题设意指背包不一定装满,若要求装满,则需要将除 \(f[0]\) 外所有 \(f[j]\) 设为 \(-\infty\)

从题意角度解释,就是空间为0的背包始终视作是装满的。

也可以手算模拟,看内层循环, \(i=1\) 时,仅有 \(f[c[i]]=w[i]\) ,其余仍为负无穷。可以推断外层循环结束后,此时只要非负即可视作对于容量为 \(j\) 的背包装满。

完全背包问题

题目

一个容量为V的背包,N类物品,每类都有无限个,每个物品有一个体积为c,有一个价值为v。求解背包能装入最大的价值总和。

思路

状态表示: \(f[i][j]\) 表示前i类物品每类挑选任意个放入容量为j的背包所能获得的最大价值和

状态计算:

  • 状态转移方程: \(f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]),k\in[0,\lfloor\tfrac{V}{c[i]}\rfloor]\)
  • 初始状态: \(f[i][0]=0,f[0][j]=0\)
  • 边界条件: \(j<c[i]\) 时, \(f[i][j]=f[i-1][j]\)

代码

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i <= N; i ++)
{
for(int j = 0; j <= V; j ++)
{
for(int k = 0; k <= V / c[i]; k ++)
{
f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]);
}
}
}
cout << f[N][V] << endl;

搜索剪枝

若物品i、j满足 \(c[i]<c[j]\)\(w[i]>w[j]\) ,则可以忽略物品j。该优化不能改变最坏复杂度。

降维优化

展开 \(f[i][j],f[i][j-c[i]]\) 的状态转移方程观察:

\(f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+v[i],f[i-1][j-2*c[i]]+2*v[i]...f[i-1][j-k*c[i]]+k*v[i])\)

\(f[i][j-c[i]]=max(f[i-1][j-c[i]],f[i-1][j-2*c[i]]+v[i]...f[i-1][j-k*c[i]]+(k-1)*v[i])\)

得结果 \(f[i][j]=max(f[i-1][j],f[i][j-c[i]]+v[i])\)

利用滚动数组降维,对比01背包的方程和优化知,由于此处转移方程含 \(f[i][j-c[i]]\) 所以内层循环变量j应该从小到大循环,使得 \(f[i-1][j-c[i]]\) 被更新为 \(f[i][j-c[i]]\) 进而更新 \(f[i][j]\)

二进制优化

二进制优化,在多重背包内细讲

代码

1
2
3
4
for(int i = 1; i <= N; i ++)
for(int j = c[i]; j <= V; j ++)
f[j]=max(f[j],f[j-c[i]]+v[i]);
cout << f[V] << endl;

对比01背包的代码,可以发现二者差别仅在内层循环,一个是从小到大,一个是从大到小,从状态和阶段的角度去解释,就是01背包当前状态是由上一阶段( \(i-1\) )的状态转移而来的,而完全背包的当前状态是由当前阶段已经被更新的状态( \(i\) )(体现出一类物品有无数个)和上一阶段( \(i-1\) )的状态转移而来的。

所以,因为阶段仅涉及当前和 前一个状态 所以可以使用滚动数组去优化空间

多重背包问题

题目

有 N 种物品和一个容量是V的背包,第i种物品最多有 \(c_i\) 件,每件体积是 \(v_i\) ,价值是 \(w_i\) 。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

思路

状态表示: \(f[i][j]\) 表示前i类物品每类挑选不大于 \(s[i]\) 个放入容量为j的背包所能获得的最大价值和

状态计算:

  • 状态转移方程: \(f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]),k\in[0,s[i]]\)
  • 初始状态: \(f[i][0]=0,f[0][j]=0\)
  • 边界条件: \(j<c[i]\) 时, \(f[i][j]=f[i-1][j]\)

代码

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i <= N; i ++)
{
for(int j = 0; j <= V; j ++)
{
for(int k = 0; k <= V / c[i]; k ++)
{
f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]);
}
}
}
cout << f[N][V] << endl;

二进制优化

所谓的二进制优化,实质上是把多重背包转换成了01背包,转换时使用到二进制。

显然的,每一个十进制整数都可以表示成二进制形式,写成按位权和展开的形式。考虑第 \(i\) 类物品,对于 \(c[i]\) 个物品,我们将 \(c[i]\) 表示成 \(c[i]=a_0*2^0+a_1*2^1+a_2*2^2+...+a_k*2^k+C,a_i=0或1\) ,也就是说将 \(c[i]\) 件物品拆分,并按照 \(1,2,4,8,16...2^k\) 组合成新的一类物品。对于新的第 \(i\) 个物品, \(a_i=0\) 是不取,反之为取。通过这样的操作,实质上我们可以组合出取任意件第 \(i\) 类物品的情况。对于所有的物品进行此项操作后,问题转换成01背包

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[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] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0)
{
cnt ++ ;
v[cnt] = a * s;
w[cnt] = b * s;
}
}

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;
}

单调队列优化

由于本篇标题为背包基础,所以在这里就不深入阐述了,大概会再发一篇背包进阶来阐述这一部分以及其他类型的背包。(咕咕咕咕咕

练习题

传送门->Warma的硬币

----- 本文结束 感谢阅读 -----
0%