现在的位置: 首页 > 综合 > 正文

背包问题九讲笔记_01背包

2013年10月19日 ⁄ 综合 ⁄ 共 3885字 ⁄ 字号 评论关闭

讲解的很详细的一篇文章:http://blog.csdn.net/insistgogo/article/details/8579597

摘自Tianyi Cui童鞋的《背包问题九讲》,稍作修改,方便理解。

01背包问题描述

已知:有一个容量为V的背包和N件物品,第i件物品的重量是weight[i],收益是cost[i]。

限制:每种物品只有一件,可以选择放或者不放

问题:在不超过背包容量的情况下,最多能获得多少价值或收益

相似问题:在恰好装满背包的情况下,最多能获得多少价值或收益

这里,我们先讨论在不超过背包容量的情况下,最多能获得多少价值或收益。

基本思路

01背包的特点:每种物品只有一件,可以选择放或者不放

子问题定义状态

  1. f[i][v] : 前i件物品放到一个容量为v的背包中可以获得最大价值  

状态转移方程

  1. 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]

代码

  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. const int N = 3;//物品个数  
  5. const int V = 5;//背包最大容量  
  6. int weight[N + 1] = {0,3,2,2};//物品重量  
  7. int value[N + 1] = {0,5,10,20};//物品价值  
  8.   
  9. int f[N + 1][V + 1] = {{0}};  
  10.   
  11. int Max(int x,int y)  
  12. {  
  13.     return x > y ? x : y;  
  14. }  
  15.   
  16. /* 
  17. 目标:在不超过背包容量的情况下,最多能获得多少价值 
  18.  
  19. 子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值 
  20.  
  21. 状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]} 
  22.  
  23. 初始化:f数组全设置为0 
  24. */  
  25. int Knapsack()  
  26. {  
  27.     //初始化  
  28.     memset(f,0,sizeof(f));  
  29.     //递推  
  30.     for (int i = 1;i <= N;i++) //枚举物品  
  31.     {  
  32.         for (int j = weight[i];j <= V;j++) //枚举背包容量,这里j的起始位置是优化过的,也可以从0开始  
  33.         {  
  34.             f[i][j] = f[i - 1][j];  
  35.             if (j >= weight[i])  
  36.             {  
  37.                 f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]);  
  38.             }  
  39.         }  
  40.     }  
  41.     return f[N][V];  
  42. }  
  43.   
  44. int main()  
  45. {  
  46.     cout<<Knapsack()<<endl;  
  47.     system("pause");  
  48.     return 1;  
  49. }  

效率分析:

算法的时间复杂度为O(N*V),空间复杂度也为O(N*V)。其中,N 表示物品个数,V 表示背包容量这里,时间复杂度不可以在优化了,但是空间复杂度可以继续优化到O(V)

优化空间复杂度

上述的方法,我们使用二维数组 f[i][v] 保存中间状态,这里我们可以使用一维数组f[v]保存中间状态就能得到结果

分析

我们现在使用f[v]保存中间状态,我们想要达到的效果是,第i次循环后,f[v]中存储的是前i个物体放到容量v时的最大价值

在回顾下之前讲过的状态转移方程:

  1. 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开始存储的。

伪代码

  1. for i=1..N //枚举物品  
  2.     for v=V..0 //枚举容量,从大到小  
  3.         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背包,按照增序枚举背包容量是不对的。

代码

  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. const int N = 3;//物品个数  
  5. const int V = 5;//背包最大容量  
  6. int weight[N + 1] = {0,3,2,2};//物品重量  
  7. int value[N + 1] = {0,5,10,20};//物品价值  
  8.   
  9. int f[V + 1] = {0};  
  10.   
  11. int Max(int x,int y)  
  12. {  
  13.     return x > y ? x : y;  
  14. }  
  15.   
  16. /* 
  17. 目标:在不超过背包容量的情况下,最多能获得多少价值 
  18.  
  19. 子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值 
  20.  
  21. 状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]} 
  22.  

抱歉!评论已关闭.