讲解的很详细的一篇文章:http://blog.csdn.net/insistgogo/article/details/8579597
摘自Tianyi Cui童鞋的《背包问题九讲》,稍作修改,方便理解。
01背包问题描述
已知:有一个容量为V的背包和N件物品,第i件物品的重量是weight[i],收益是cost[i]。
限制:每种物品只有一件,可以选择放或者不放
问题:在不超过背包容量的情况下,最多能获得多少价值或收益
相似问题:在恰好装满背包的情况下,最多能获得多少价值或收益
这里,我们先讨论在不超过背包容量的情况下,最多能获得多少价值或收益。
基本思路
01背包的特点:每种物品只有一件,可以选择放或者不放
子问题定义状态
- f[i][v] : 前i件物品放到一个容量为v的背包中可以获得最大价值
状态转移方程
- f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])
分析
考虑我们的子问题,将前i件物品放到容量为v的背包中,若我们只考虑第i件物品时,它有两种选择,放或者不放。
1) 如果第i件物品不放入背包中,那么问题就转换为:将前i - 1件物品放到容量为v的背包中,带来的收益f[i - 1][v]
2) 如果第i件物品能放入背包中,那么问题就转换为:将前i - 1件物品放到容量为v - weight[i]的背包中,带来的收益f[i - 1][v - weight[i]] + cost[i]
代码
- #include <iostream>
- using namespace std;
- const int N = 3;//物品个数
- const int V = 5;//背包最大容量
- int weight[N + 1] = {0,3,2,2};//物品重量
- int value[N + 1] = {0,5,10,20};//物品价值
- int f[N + 1][V + 1] = {{0}};
- int Max(int x,int y)
- {
- return x > y ? x : y;
- }
- /*
- 目标:在不超过背包容量的情况下,最多能获得多少价值
- 子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值
- 状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]}
- 初始化:f数组全设置为0
- */
- int Knapsack()
- {
- //初始化
- memset(f,0,sizeof(f));
- //递推
- for (int i = 1;i <= N;i++) //枚举物品
- {
- for (int j = weight[i];j <= V;j++) //枚举背包容量,这里j的起始位置是优化过的,也可以从0开始
- {
- f[i][j] = f[i - 1][j];
- if (j >= weight[i])
- {
- f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]);
- }
- }
- }
- return f[N][V];
- }
- int main()
- {
- cout<<Knapsack()<<endl;
- system("pause");
- return 1;
- }
效率分析:
此算法的时间复杂度为O(N*V),空间复杂度也为O(N*V)。其中,N 表示物品个数,V 表示背包容量这里,时间复杂度不可以在优化了,但是空间复杂度可以继续优化到O(V)
优化空间复杂度
上述的方法,我们使用二维数组 f[i][v] 保存中间状态,这里我们可以使用一维数组f[v]保存中间状态就能得到结果
分析
我们现在使用f[v]保存中间状态,我们想要达到的效果是,第i次循环后,f[v]中存储的是前i个物体放到容量v时的最大价值
在回顾下之前讲过的状态转移方程:
- f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])
我们可以看到,要想得到 f[i][v],我们需要知道 f[i - 1][v] 和 f[i - 1][v - weight[i]],由于我们使用二维数组保存中间状态,所以可以直接取出这两个状态。
当我们使用一维数组存储状态时,f[v]表示,在执行i次循环后(此时已经处理i个物品),前i个物体放到容量v时的最大价值,即之前的f[i][v]。与二维相比较,它把第一维隐去了,但是二者表达的含义还是相同的,只不过针对不同的i,f[v]一直在重复使用,所以,也会出现第i次循环可能会覆盖第i - 1次循环的结果。
为了求f[v],我们需要知道,前i - 1个物品放到容量v的背包中带来的收益,即之前的f[i - 1][v] 和 前i - 1件物品放到容量为v - weight[i]的背包中带来的收益,即之前的f[i - 1][v - weight[i]] + cost[i]。
难点:由于我们只使用一维数组存储,则在求这两个子问题时就没有直接取出那么方便了,因为,第i次循环可能会覆盖第i - 1次循环的结果。
现在我们来求这两个值
1)前i - 1个物品放到容量v的背包中带来的收益,即之前的f[i - 1][v] :
由于,在执行在i次循环时,f[v]存储的是前i个物体放到容量v时的最大价值,在求前i个物体放到容量v时的最大价值(即之前的f[i][v])时,我们是正在执行第 i 次循环,f[ v ]的值还是在第 i - 1 次循环时存下的值,在此时取出的 f[ v ]就是前i - 1个物体放到容量v时的最大价值,即f[i - 1][v]。
2)前i - 1件物品放到容量为v - weight[i]的背包中带来的收益,即之前的f[i - 1][v - weight[i]] + cost[i]
由于,在执行第i次循环前,f[0 ~ V]中保存的是第i - 1次循环的结果,即是前i - 1个物体分别放到容量0 ~ V时的最大价值,即f[i - 1][0 ~ V]。
则,在执行第i次循环前,f 数组中v - weight[i]的位置存储就是我们要找的 前i - 1件物品放到容量为v - weight[i]的背包中带来的收益 (即之前的f[i - 1][v - weight[i]]),这里假设物品是从数组下标1开始存储的。
伪代码
- for i=1..N //枚举物品
- for v=V..0 //枚举容量,从大到小
- f[v]=max{f[v],f[v-weight[i]] + cost[i]};
由上面伪代码可知,在执行第 i 次循环时,需要把背包容量由V..0都要遍历一遍,检测第 i 件物品是否能放。
逆序枚举容量的原因:
注意一点,我们是由第 i - 1 次循环的两个状态推出 第 i 个状态的,而且 v > v - weight[i],则对于第i次循环,背包容量只有当V..0循环时,才会先处理背包容量为v的状况,后处理背包容量为 v-weight[i] 的情况。
具体来说,由于,在执行v时,还没执行到v - weight[i]的,因此,f[v - weight[i]]保存的还是第i - 1次循环的结果。即在执行第i次循环 且 背包容量为v时,此时的f[v]存储的是 f[i - 1][v] ,此时f[v-weight[i]]存储的是f[i - 1][v-weight[i]]。
相反,如果在执行第 i 次循环时,背包容量按照0..V的顺序遍历一遍,来检测第 i 件物品是否能放。此时在执行第i次循环 且 背包容量为v时,此时的f[v]存储的是 f[i - 1][v] ,但是,此时f[v-weight[i]]存储的是f[i][v-weight[i]]。
因为,v > v - weight[i],第i次循环中,执行背包容量为v时,容量为v - weight[i]的背包已经计算过,即f[v - weight[i]]中存储的是f[i][v - weight[i]]。即,对于01背包,按照增序枚举背包容量是不对的。
代码
- #include <iostream>
- using namespace std;
- const int N = 3;//物品个数
- const int V = 5;//背包最大容量
- int weight[N + 1] = {0,3,2,2};//物品重量
- int value[N + 1] = {0,5,10,20};//物品价值
- int f[V + 1] = {0};
- int Max(int x,int y)
- {
- return x > y ? x : y;
- }
- /*
- 目标:在不超过背包容量的情况下,最多能获得多少价值
- 子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值
- 状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]}