`
blue2048
  • 浏览: 183715 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

讲透完全背包算法

阅读更多

 

1、问题描述

 

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

条件:每种物品都有无限件,能放多少就放多少。

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

举例:物品个数N = 3,背包容量为V = 5,则背包可以装下的最大价值为40.

----------------------------------------------

2、基本思路(直接扩展01背包的方程)

由于本问题类似于01背包问题,在01背包问题中,物品要么取,要么不取,而在完全背包中,物品可以取0件、取1件、取2件...直到背包放不下位置。因此,可以直接在01背包的递推式中扩展得到。

 

[cpp] view plaincopy
 
  1. f[i][v]:表示前i件物品放入容量为v的容量中时的最大收益  
  2. 递推式:  
  3. f[i][v] = max(f[i - 1][v],f[i - K * weight[i]] + K * Value[i]); 其中  1 <= K * weight[i] <= v,(v指此时背包容量)  
  4. //初始条件  
  5. f[0][v] = 0;  
  6. f[i][0] = 0;  

代码:

 

 

[cpp] view plaincopy
 
  1. #include <iostream>  
  2. #include <assert.h>  
  3. using namespace std;  
  4. /* 
  5. f[i][v]:前i件物品放入背包容量为v的背包获得的最大收益 
  6.  
  7. f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Wi] + k * Vi,其中 1<=k<= v/Wi) 
  8.  
  9. 边界条件 
  10. f[0][v] = 0; 
  11. f[i][0] = 0; 
  12. */  
  13.   
  14. const int N = 3;  
  15. const int V = 5;  
  16. int weight[N + 1] = {0,3,2,2};  
  17. int Value[N + 1] = {0,5,10,20};  
  18.   
  19. int f[N + 1][V + 1] = {0};  
  20.   
  21. int Completeknapsack()  
  22. {  
  23.     //边界条件  
  24.     for (int i = 0;i <= N;i++)  
  25.     {  
  26.         f[i][0] = 0;  
  27.     }  
  28.     for (int v = 0;v <= V;v++)  
  29.     {  
  30.         f[0][v] = 0;  
  31.     }  
  32.     //递推  
  33.     for (int i = 1;i <= N;i++)  
  34.     {  
  35.         for (int v = 1;v <= V;v++)  
  36.         {  
  37.             f[i][v] = 0;  
  38.             int nCount = v / weight[i];  
  39.             for (int k = 0;k <= nCount;k++)  
  40.             {  
  41.                 f[i][v] = max(f[i][v],f[i - 1][v - k * weight[i]] + k * Value[i]);  
  42.             }  
  43.         }  
  44.     }  
  45.     return f[N][V];  
  46. }  
  47.   
  48. int main()  
  49. {  
  50.     cout<<Completeknapsack()<<endl;  
  51.     system("pause");  
  52.     return 1;  
  53. }  

复杂度分析:

程序需要求解N*V个状态,每一个状态需要的时间为O(v/Weight[i]),总的复杂度为O(NV*Σ(V/c[i]))。

代码优化:

完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。

即,如果一个物品A是占的地少且价值高,而物品B是占地多,但是价值不怎么高,那么肯定是优先考虑A物品的。

这里代码略。

----------------------------------------------

3、转换为01背包问题求解(直接利用01背包)

思路 1、完全背包的物品可以取无限件,根据背包的总容量V和第i件物品的总重量Weight[i],可知,背包中最多装入V/Weight[i](向下取整)件该物品。因此可以直接改变第i件物品的总个数,使之达到V/Weight[i](向下取整)件,之后直接利用01背包的思路进行操作即可。

举例:物品个数N = 3,背包容量为V = 5。

拆分之前的物品序列:


拆分之后的物品序列:


根据上述思想:在背包的最大容量(5)中,最多可以装入1件物品一,因此不用扩展物品一。最多可以装入2件物品二,因此可以扩展一件物品二。同理,可以扩展一件物品三。

时间复杂度的分析:O(NNew*V),其中V表示扩展前背包容量,NNew表示扩展后物品的个数,NNew =Σ(V/Weight[i](向下取整))

思路 2、对物品进行拆分时,拆成二进制的形式。

具体思路:把第i种物品拆成费用为weight[i]*2^k、价值为w[i]*2^k的若干件物品,其中k满足weight[i]*2^k<=V。

思路:这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。

这样把每种物品拆成O(log V/weight[i])件物品,是一个很大的改进。

举例:物品个数N = 3,背包总容量为V = 5。
拆分之前的物品序列:


拆分之后的物品序列:


为了和前面的例子保持一致,这里才用之前的例子,但是这个例子没有更好的说明二进制的拆分方法拆分的物品个数会少写。

假设物品A的重量为2,收益为3,背包的总重量为20。

根据第一种拆分,可以拆成10个物品,每一个物品的重量为2,收益为3。

根据第二种拆分方法,可以拆成4个物品,分别是物品一(重量为1*2,收益为3),物品二(重量为2*2,收益为6),物品三(重量为4*2,收益为12),物品四(重量为8*2,收益为24)。

时间复杂度的分析:O(NNEW*V),其中V表示扩展前背包容量,NNew表示扩展后物品的个数,NNew = Σ(log V/weight[i](向下取整))

代码:

 

[cpp] view plaincopy
 
  1. #include <iostream>  
  2. #include <vector>  
  3. #include <assert.h>  
  4. using namespace std;  
  5. /* 
  6. f[v]:表示第i件物品放入容量为v的背包后,获得的最大容量 
  7. f[v] = max(f[v],f[v - weight[i]] + value[i]); 
  8. 初始条件:f[0] = 0; 
  9. */  
  10.   
  11. const int N = 3;  
  12. const int V = 20;//5  
  13. int weight[N + 1] = {0,3,2,2};  
  14. int Value[N + 1] = {0,5,10,20};  
  15.   
  16. int NNew = 0;  
  17. vector<int> weightVector;  
  18. vector<int> Valuevector;  
  19. int f[V + 1] = {0};  
  20. /*拆分物品*/  
  21. void SplitItem()  
  22. {  
  23.     //从1开始  
  24.     weightVector.push_back(0);  
  25.     Valuevector.push_back(0);  
  26.     //开始拆分  
  27.     int nPower = 1;  
  28.     for (int i = 1;i <= N;i++)  
  29.     {  
  30.         nPower = 1;  
  31.         while (nPower * weight[i] <= V)  
  32.         {  
  33.             weightVector.push_back(nPower * weight[i]);  
  34.             Valuevector.push_back(nPower * Value[i]);  
  35.             nPower <<= 1;  
  36.         }  
  37.     }  
  38. }  
  39.   
  40. int Completeknapsack()  
  41. {  
  42.     //拆分物品  
  43.     SplitItem();  
  44.     //转化为01背包处理  
  45.     NNew = weightVector.size() - 1;//多加了一个0,要减去  
  46.   
  47.     for (int i = 1;i <= NNew;i++)//物品个数变化  
  48.     {  
  49.         for (int v = V;v >= weightVector[i];v--)//背包容量仍是V  
  50.         {  
  51.             f[v] = max(f[v],f[v - weightVector[i]] + Valuevector[i]);  
  52.         }  
  53.     }  
  54.   
  55.     return f[NNew];  
  56. }  
  57. int main()  
  58. {  
  59.     cout<<Completeknapsack()<<endl;  
  60.     system("pause");  
  61.     return 1;  
  62. }  

4、O(VN)的算法

 

伪代码

 

[cpp] view plaincopy
 
  1. for (int i = 1;i <= N;i++)  
  2. {  
  3.     for (int v = weight[i];v <= V;v++)  
  4.     {  
  5.         f[v] = max(f[v],f[v - weight[i]] + Value[i]);  
  6.     }  
  7. }  

分析:这和01背包的伪代码很相似,在01背包的代码中,v变化的区间是逆序循环的,即[V,Weight[i]]。而这里,v变化的区间是顺序循环的,即为[Weight[i],V]。

 

原因:

再次给出定义:

f[i][v]表示把前i件物品放入容量为v的背包时的最大代价。

f[i-1][v-c[i]]表示把前i - 1件物品放入容量为v的背包时的最大代价.

在01背包中,v变化的区间是逆序循环的原因:要保证由状态f[i-1][v-c[i]]递推状态f[i][v]时,f[i-1][v-c[i]]没有放入第i件物品。之后,在第i循环时,放入一件第i件物品。

01背包的方程:

[cpp] view plaincopy
 
  1. f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + Value[i])    

 

在完全背包中,v变化的区间是顺序循环的原因完全背包的特点是每种物品可选无限件,在求解加选第i种物品带来的收益f[i][v]时,在状态f[i][v-c[i]]中已经尽可能多的放入物品i了,此时在f[i][v-c[i]]的基础上,我们可以再次放入一件物品i,此时也是在不超过背包容量的基础下,尽可能多的放入物品i。

完全背包的方程:

 

[cpp] view plaincopy
 
  1. f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);  

举例:

物品个数N = 3,背包总容量为V = 5。

物品信息:


完全背包:


分析:

i = 2,表示正在处理第2件物品。在求解f[2][4]时,如果要计算把第2件物品放入背包后的代价时,我们需要知道f[2][2],此时f[2][2]中已经尽全力放入第2件物品了(已经放入一件)。此时此刻还可以在放入一件第2件物品,在背包容量为4时,最多可以放入两件第二件物品。

总结下,f[i][v]:表示在背包容量为v时,尽全力的放入第i件物品的代价。f[i][v - weight[i]]:表示在背包容量为v - weight[i]时,尽全力的放入第i件物品的代价。因此由f[i][v - weight[i]]转换为f[i][v]时,也是在f[i][v - weight[i]]的基础上有加入了一件物品i。

为了节省保存状态的空间,可以直接使用一维数组保存状态。

代码:迭代方程:f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);

 

[cpp] view plaincopy
 
  1. #include <iostream>  
  2. #include <vector>  
  3. #include <assert.h>  
  4. using namespace std;  
  5. const int N = 3;  
  6. const int V = 5;//5  
  7. int weight[N + 1] = {0,3,2,2};  
  8. int Value[N + 1] = {0,5,10,20};  
  9.   
  10. int f[N + 1][V + 1] = {0};  
  11.   
  12. int Completeknapsack()  
  13. {  
  14.     //初始化  
  15.     for (int i = 0;i <= N;i++)  
  16.     {  
  17.         f[i][0] = 0;  
  18.     }  
  19.     for (int v = 0;v <= V;v++)  
  20.     {  
  21.         f[0][v] = 0;  
  22.     }  
  23.     for (int i = 1;i <= N;i++)  
  24.     {  
  25.         for (int v = weight[i];v <= V;v++)  
  26.         {  
  27.             f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);  
  28.         }  
  29.     }  
  30.     return f[N][V];  
  31. }  
  32.   
  33. int main()  
  34. {  
  35.     cout<<Completeknapsack()<<endl;  
  36.     system("pause");  
  37.     return 1;  
  38. }  

代码:迭代方程:f[v] = max(f[v],f[v - weight[i]] + Value[i]);

 

 

[cpp] view plaincopy
 
  1. #include <iostream>  
  2. using namespace std;  
  3. const int N = 3;  
  4. const int V = 5;//5  
  5. int weight[N + 1] = {0,3,2,2};  
  6. int Value[N + 1] = {0,5,10,20};  
  7.   
  8. int f[V + 1] = {0};  
  9.   
  10. int Completeknapsack()  
  11. {  
  12.     f[0] = 0;  
  13.     for (int i = 1;i <= N;i++)  
  14.     {  
  15.         for (int v = weight[i];v <= V;v++)  
  16.         {  
  17.             f[v] = max(f[v],f[v - weight[i]] + Value[i]);  
  18.         }  
  19.     }  
  20.     return f[V];  
  21. }  
  22. int main()  
  23. {  
  24.     cout<<Completeknapsack()<<endl;  
  25.     system("pause");  
  26.     return 1;  
  27. }  

转自 http://blog.csdn.net/insistgogo/article/details/11081025

 

分享到:
评论

相关推荐

    背包 背包问题 背包算法

    问题可以分为0-1背包、完全背包和多重背包三种类型,每种类型有不同的解题策略。 1. 0-1背包:每种物品只能选择0个或1个放入背包。 2. 完全背包:每种物品可以无限次放入背包,只要不超过背包容量。 3. 多重背包:...

    Java背包算法规划求解

    6. **完全背包与多重背包**:在实际问题中,可能会遇到每种商品可以无限购买(完全背包)或有限购买(多重背包)的情况。这些情况需要修改状态转移方程,以适应不同限制。 7. **回溯法**:除了动态规划,回溯法也是...

    matlab程序(解决0-1背包问题).zip_背包_背包算法 matlab_背包问题_遗传算法 背包_遗传算法背包

    这个问题的难点在于物品的选择是二元决策,即每件物品要么被完全放入背包,要么完全不放入,因此得名0-1背包问题。 遗传算法是一种模拟自然选择和遗传机制的全局优化方法,它通过模拟生物进化过程中的“适者生存”...

    基于0-1背包算法的社交网络行为隐写术.docx

    基于0-1背包算法的社交网络行为隐写术 本文提出了一种基于0-1背包算法的社交网络行为隐写术,以解决传统隐写术的安全性问题。该方法通过引入0-1背包人员分配协议,降低了发送者和接收者有较多的共同好友这一限制...

    C++ 编写的背包算法程序 动态规划

    C++编写的背包算法程序 cpp 动态规划

    PHP 01背包算法

    用 PHP 实现的 01 背包算法,参考了网上的相关 C++ 算法,用来方便 PHP 程序员改造使用,我是用它来实现在指定宽度的栏中整齐的排列一堆标签云,效果非凡且神奇,初次使用时一瞬间的确有这样的感觉。

    贪心算法 背包问题 C语言

    贪心算法是一种优化策略,它在每...在背包问题中,贪心算法对于某些特定类型的问题(如完全背包、非递减价值密度的物品)能得到最优解,但对于一般部分背包问题,可能需要结合动态规划等更强大的工具来确保全局最优。

    beibao.rar_背包 问题_背包算法 matlab_背包算法MATLAB_贪婪算法_贪婪算法 MATLAB

    此问题有多种变体,如完全背包问题(可以无限次选择同一种物品)、0-1背包问题(每种物品只能选一次)等。 MATLAB作为一款强大的数值计算和图形处理软件,提供了丰富的工具和函数支持算法的实现。在这个项目中,...

    贪心算法 背包问题 c语言

    ### 贪心算法在背包问题中的应用及C语言实现 #### 一、贪心算法简介 贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过一系列的局部最优选择来达到全局最优解的目的。它适用于某些特定的问题类型,在...

    遗传算法解决背包问题

    本项目中,遗传算法被应用于解决经典的背包问题,这是一种典型的组合优化问题。在背包问题中,我们通常有一组物品,每件物品都有一个重量和价值,目标是在不超过背包总容量的前提下,选取物品以最大化总价值。 首先...

    算法-动态规划- 背包问题 P04- 混合背包(包含源程序).rar

    混合背包问题是一个更复杂的背包问题变种,它结合了0-1背包和完全背包的特点。在0-1背包问题中,每种物品只能选择放入背包一次或不放入;而在完全背包问题中,每种物品可以无限次地放入背包。混合背包则允许每种物品...

    算法背包9讲

    根据问题的具体设定,背包问题可以分为多个变种:0-1背包、完全背包、多重背包等。 1. **0-1背包**:每个物品只能选择一次,即要么全部放入背包,要么不放。这种情况下,我们需要通过贪心策略或动态规划来求解最优...

    这个是背包算法,解决背包问题的java代码

    这个是背包算法。。解决背包问题的java代码。。。。。。。。。。。。。。。。。。。。。。

    MH背包密码算法算法原理与实现_密码学源代码_C语言程序_C++程序源代码.zip

    通过对“MH背包密码算法”的原理学习和源代码实践,不仅可以掌握一种非对称加密方法,还能锻炼C/C++编程能力。然而,密码学发展迅速,安全性更高的算法不断出现,因此,持续学习和了解最新密码学技术至关重要。同时...

    算法参考资料背包九讲算法参考资料背包九讲

    在实际应用中,背包问题还有许多变种,如分数背包问题、多重背包问题、完全背包问题等,每种变种都有其特定的解法和应用场景。例如: - 分数背包问题允许将物品分割成更小的部分来装入背包。 - 多重背包问题考虑的...

    背包问题PSO算法代码

    粒子群优化算法(PSO)是一种启发式优化技术,其灵感来源于自然...对于希望在优化问题中使用PSO算法的研究者和工程师而言,理解PSO算法在0-1背包问题上的应用,有助于在实际中更有效地运用这一算法来解决各种优化问题。

    贪心算法 多重背包

    用贪心算法解决多重背包问题的C++解决方法

    0-1背包算法(动态规划)

    0-1背包问题是一种经典的组合优化问题,在计算机科学和运筹学中有着广泛的应用。...在实际编程中,可以使用Python、Java等编程语言实现这个算法,并通过输入不同的物品和背包承重,测试算法的正确性和效率。

    背包问题算法源码(c语言)

    10. **拓展应用**:背包问题有多种变体,如完全背包(每个物品可以无限数量放入)、多重背包(每个物品有有限数量)等,可以根据实际需求进行扩展。 通过学习和理解这些知识点,你将能够实现一个功能完善的C语言...

    毕业论文jsp30背包算法.doc

    背包算法在计算机科学中的应用 背包算法是计算机科学中的一种经典算法,用于解决组合优化问题。该算法的提出可以追溯到1978年,Merkel和Hellman提出了该问题。该算法的主要思想是,在给定总重量的限制下,如何选择...

Global site tag (gtag.js) - Google Analytics