背包九讲

发表于 | 更新于: | 分类于
字数统计: 1.8k | 阅读时长 ≈ 7

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%