背包九讲

0/1背包问题

有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大?

将每一件物品从1到n编号,从第1件物品开始,每一件物品就只有两个状态:放进背包了 / 没有放进背包。

我们画一张表格,行对应着每一件物品,列对应着背包的重量,那么pack[i][j]就表示 前i件物品,背包最大承重j 这个子问题的解。

给一组数据作为样例:

5 10
6 2
3 2
5 6
4 5
6 4

第一行表示有5件物品,10为最大承重,2-6行为5个物品的价值和重量。

生成以下的表格

0    6    6    6    6     6     6     6     6     6
0    6    6    9    9     9     9     9     9     9
0    6    6    9    9     9     9    11    11    14
0    6    6    9    9     9    10    11    13    14
0    6    6    9    9    12    12    15    15    15

 所以最终的结果是最后一行最后一列的 15

给出代码:

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

/* 01 package problem */

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int pack[100][1000];
int c[100],w[100];

void make(int n, int r){
memset(pack,0,sizeof(pack));
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= r; j++)
pack[i][j] = max(pack[i - 1][j - c[i]] + w[i], pack[i - 1][j]);
cout<<pack[n][r];
}

int main(){
int t,n,V;
cin>>t;
while(t--){ //多组数据
cin>>n>>V;
for (int i = 1; i <= n; i++)
cin>>c[i]>>w[i];
make(n,V);
}
return 0;
}

代码优化

这个代码在时间上应该已经不能再优化了,但是还可以考虑空间复杂度的优化。

优化的基本思路:

考虑所用到的状态转移方程: pack[i][j] = max(pack[i-1][j-c[i]] + w[i], pack[i-1][j]); 可以发现 pack[i][j] 的值并不和整个二维表的每一个数字的值都有关,而是仅仅和上面一行的值有关,所以可以使用 pack[2][n] 这么大的数组来存储结果。

考虑状态转移方程的实际情况,还可以使用一维数组来进行运算,但是要注意的是,此时,循环应该从后往前进行。因为如果是按从前往后的顺序,那么 pack[i][j] = max(pack[i][j-c[i]] + w[i] , pack[i][j]); 中进行比较的两个值 pack[i][j] 是没有更新的,也就是 pack[i-1][j] 的值,而 pack[i][j - c[i]]一定是前面被更新过的,也就是 pack[i][j-w[i]] 的值。这就是说,max() 比较的两个数是属于原来二维数组中不同的两行,而不是我们期望的相同的两行。

如果上面的说法不能理解我们不妨这样:有一件物品的性价比很高,在pack数组的某个位置,我们第一次将这个物品放入背包中,但是按照从前往后的顺序,很可能在这个位置的后面某个位置我们会再次将这个物品添加进去。

优化后的代码

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

using namespace std;

int pack[10000],c[1000],w[1000];

void make(int n, int r){
memset(pack,0,sizeof(pack));
for (int i = 1; i <= n; i++)
for (int j = r; j >= w[i]; j--)
pack[j] = max(pack[j], pack[j - c[i]] + w[i]);
cout<<pack[r]<<endl;
}

int main(){
int n,t,V;
cin>>t;
while(t--){
cin>>n>>V;
for (int i = 1; i <= n; i++) cin>>c[i]>>w[i];
make(n,V);
}
return 0;
}

初始化问题:

  • 如果限定背包必须装满,那么需要将数组初始化为 -∞ (负无穷大)

  • 如果背包可以不装满,那么数组初始化为0

为了后面的书写方便,我们把代码改成这样

1
2
3
4
void ZeroOnePack(int c,int w){
for (int i = V; i >= c; i--)
pack[i] = max(pack[i], pack[i - c] + w);
}

这样01背包问题的主要代码就是这样:

1
2
for (int i = 0; i < n; i++)
ZeroOnePack(c[i],w[i]);

这样ZeroOnePack()这个函数就专门解决了“放一个物品”的问题

完全背包问题

完全背包问题和0/1背包问题几乎一模一样,不同的就是物品不再是一个,而是无数个

思路

完全背包不同处是原来的一个物品变成了无数个,但是我们还是可以把它变成0/1背包问题的,试想一下,即使拥有无数个物品,但是真的可以用无数个吗?

不可能,因为背包的容量有限,所以每个物品c,w最多可以使用[V/c]个,所以以下面的数据为例:

c:    3    2    5    4
w:    7    4    2    5
V = 10

我们完全可以把这组数据改成这样:

c:    3    3    3    2    2    2    2    2    5    5    4    4
w:    7    7    7    4    4    4    4    4    2    2    5    5

原因自然是背包容量最大为10,所以占用空间为3的物品最多放3个,修改过后的数据就可以用0/1背包的方法处理

那难道完全背包需要重开一个c2[],w2[],然后按0/1背包处理吗?

当然不是,还记得我们将0/1背包进行优化时说的如果循环从前向后进行会发生什么后果吗?

这一句 “但是按照从前往后的顺序,很可能在这个位置的后面某个位置我们会再次将这个物品添加进去。”

看到了?0/1背包时为了避免重复,我们将循环改为从后往前,但是完全背包是可以重复使用物品的,对吧?所以代码:

1
2
3
4
void CompletePack(c,w){
for (int i = c; i <= V; i++)
pack[i] = max(pack[i],pack[i - c] + w )
}

怎么样,和0/1背包只有一点点的差别对不对?

3.多重背包问题

多重背包和0/1背包不同的地方就是物品不是一个而是有m个

所以我们还是就一个物品c,w,m分析:

对于m可能有两种情况:

  1. m >= [V/c],这种情况明显是完全背包
  2. 0 < m < [v/c],对于这种情况需要认真分析一下

我们仍然需要按照0/1背包的思路把这些物品拆开,而且我们要保证我们拆出来的这些物品可以通过组合表示出1到m任意件物。

我们可以考虑二进制的计数方法,这样我们把物品拆成(c,w) , (2c,2w) , (4c,4w) …… [(m-2^k)*c , (m-2^k)*w)]

不管最优解会在这件物品中取几件,我们都可以用我们拆出来的这些物品来表示(请自己证明,二进制的思想)

所以,有了思路,代码就简单了:

1
2
3
4
5
6
7
8
9
10
11
12
13
void MultiplePack(c,w,m){
if (c * m >= V) {
CompletePack(c,w);
return;
}
k = 1;
while (k < m) {
ZeroOnePack(c*k,w*k);
m = m - k;
k = 2 * k;
}
ZeroOnePack(c * m, w * m);
}

其实就是0/1背包和完全背包的组合,有木有?

未完待续……

0%