简述

背包问题(Knapsack problem)是一种组合优化的NP完全问题。

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高

由于其下又可以从浅入深地进行分类，所以此处也分类讨论。

0-1背包

问题与dp求解

有NN 件物品和一个容量为VV 的背包。第ii 件物品的体积是c[i]c[i]，价值是w[i]w[i]。求解将哪些物品装入背包可使价值总和最大.

问题特点： 每种物品仅有一件，可以选择放或不放，用子问题定义状态：即f(i,v)f(i,v)表示前ii 件物品放入一个容量为vv 的背包可以获得的最大价值。

注：背包容量和物体容量有可能直接是0

由此，利用动态规划方法，可以得到该问题的 状态转移方程：

f(i,v)=max⁡{f(i−1,v),f(i−1,v−ci)+wi}f(i,v)=\max{\{f(i-1,v),f(i-1,v-c_i)+w_i\}}

即是：

如果放第ii 个物品到容量是vv 的背包里，那么其价值为 前i−1i-1 个物品放进容量是v−civ-c_i的背包的最大价值再加上ii 物品本身的价值wiw_i；

如果不放，那么当前最大价值就是前i−1i-1个物品放进容量为vv 的背包所获得的价值。

上述两种情况，谁的结果最大，当前状态的最大价值就取谁。

为了方便解说，此处以HDOJ2602(Bone Collector)为例进行剖析。Bone Collector|原题地址

如下表所示，W 表示放入的某种品类的骨头的价值，C 表示该骨头的体积，横坐标表示待放入背包的体积：

(W,C)012345678910
000000000000
(1,5)00000111111
(2,4)00002222233
(3,3)00033335555
(4,2)00444777799
(5,1)0559991212121214

以第二行为例，可知，当背包体积大于该骨头的体积 C=5 时，可以将其放入；

以第6行第6列为例，可知，当前最大价值等于【第5行第4列】的价值+当前骨头的价值；

以此类推……

综上，可以得到如下的C代码：

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
#include<iostream>
#include<string.h>
using namespace std;
int dp[1001][1001];
struct Goods{
	int w;//价值
	int v;//体积volmue
}goods[1002]; 
int main(void){
	int T;
	int n,m;
	cin >> T;
	while(T--){
		cin >> n >> m;
		memset(dp,0,sizeof(dp));
		memset(goods,0,sizeof(goods));
		for(int i = 1; i <= n; i++){cin >> goods[i].w;}
		for(int i = 1; i <= n; i++){cin >> goods[i].v;}
		for(int i = 1; i <= n; i++){
			for(int j = 0; j <= m; j++){
				if(j - goods[i].v >= 0)
					dp[i][j] = max(dp[i-1][j],dp[i-1][j-goods[i].v]+goods[i].w);
				else{dp[i][j] = dp[i-1][j];} //放不下就没得放了
			}
		}
		cout << dp[n][m] << endl;
	}
	return 0;
}

易知，本方法的时间复杂度是N×VN\times V，即骨头种类×背包体积，而空间复杂度也是N×VN\times V

从表中也可以看出，有大量的位置是空白的。由此，考虑直接用一维数组来完成对dp的求解~

优化空间复杂度

以第一种骨头（1，5）为例，得到其表：

(V,C)012345678910
000000111111

我们知道，在考虑算第二种骨头的时候，可能需要用到第一个骨头的数据，并且值得注意的是，随着我们考虑的骨头越来越多，价值只增不减，从上面的代码也可以看出，最后要的结果只需是 dp[n][m]，之前的中间数据是可以不需要的。

因此，可以直接在计算第二种骨头的时候将第一个数组覆盖。

状态方程更改为：

f(v)=max⁡{f(v),f(v−ci)+wi}f(v)=\max{\{f(v),f(v-c_i)+w_i\}}

其物理含义是当前背包所剩容量为vv 的情况下所能获得的最大价值f(v)f(v) 是不放入物品ii 和放入物品ii 能获得的价值中，最大的那一个。前提是我们要事先知道当前情况下不放入物品ii 的最大价值。这和前面的f(i,v)f(i,v) 中“前ii 个物品”的物理含义不同，这里是针对所有物品。

之前我们循环的伪代码如下：

1
2
3
4
for i = 1 to n//所有物品
    for j = 0 to V//从0开始遍历所有可能的背包剩余体积
        DP[i][j] = max(DP[i-1][j],DP[i-1][j-v[i]] + w[i])
        //此处不可直接改为：dp[j] = max(dp[j] , dp[j-v[i]] + w[i]);

如果我们降维成一维数组，然后jj 还是从0    to    V0\;\; to \;\;V 的话，就会出现：

先在j=v1j=v_1 的时候加过一遍“第二种骨头”，然后在计算j=v2j = v_2 的时候如果max⁡()\max() 用到了 与v1v_1有关的刚刚已经加过一次了的量，那么此时的dp[v2]dp[v_2] 就并不是在加了一次第一个骨头的情况下再加第二个骨头所得到的最大值，而是第二个骨头加了两次的情况。

同理以此类推，那么就会出现 “第ii 种骨头” 可以无限加的情况，与01背包问题不符。

因此，我们需要在更新第二个骨头的时候，保留前一个骨头的数据都能用上且不被更新过，所以，最终的解决方法就是，jj 从V    to    viV\;\;to\;\;v_i。

也就是从后往前遍历，可以保留未被更新过的数组内容。

综上，原代码可以更改为：

1
2
3
4
5
6
7
8
9
10
11
12
int dp[1001];
/*

	省略
	
*/
for(int i = 1; i <= n; i++){
    for(int j = m; j >= goods[i].v; j--){
        dp[j] = max(dp[j],dp[j-goods[i].v]+goods[i].w);
    }
}
cout << dp[m] << endl;

完全背包

问题与dp求解

1
2
3
4
for i = 1 to n//所有物品
    for j = 0 to V//从0开始遍历所有可能的背包剩余体积
        DP[i][j] = max(DP[i-1][j],DP[i][j-v[i]] + w[i])
        //注意与01背包的问题

参考资料

1.背包九讲

2.Bone Collector|HDOJ