背包问题求解方法综述

v1.0 可编辑可修改算法分析与设计大作业实验题目：0-1背包问题求解方法综述组 员：班 级：指导老师：1v1.0 可编辑可修改0-1背包问题求解方法综述【摘要】：0-1背包问题是一个经典的 NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型。本文首先对背包问题做了阐述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问题进行求解，分析了 0-1背包问题的数学模型,刻划了最优解的结构特征,建立了求最优值的递归关系式。最后对四种算法从不同角度进行了对比和总结。【关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法。引言0-1背包问题是指给定n个物品,每个物品均有自己的价值vi和重量wi(i=1,2,⋯,n),再给定一个背包,其容量为W。要求从n个物品中选出一部分物品装入背包,这部分物品的重量之和不超过背包的容量,且价值之和最大。单个物品要么装入,要么不装入。很多问题都可以抽象成该问题模型 ,如配载问题、物资调运[1]问题等,因此研究该问题具有较高的实际应用价值。目前 ,解决0-1背包问题的方法有很多,主要有动态规划法、回溯法、分支限界法、遗传算法、粒子群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。其中动态规划、回溯法、分支限界法时间复杂性比较高 ,计算智能算法可能出现局部收敛,不一定能找出问题的最优解。文中在动态规划法的基础上进行了改进 ,提出一种求解 0-1背包问题的算法,该算法每一次执行总能得到问题的最优解 ,是确定性算法,算法的时间复杂性最坏可能为 O(2n)。背包问题描述0-1背包问题(KP01)是一个著名的组合优化问题。它应用在许多实际领域 ,如项目选择、资源分布、投资决策等。背包问题得名于如何选择最合适的物品放2v1.0 可编辑可修改置于给定背包中。本文主要研究背包问题中最基础的0/1背包问题的一些解决方法。为解决背包问题，大量学者在过去的几十年中提出了很多解决方法。解决背包问题的算法有最优算法和启发式算法[2]，最优算法包括穷举法、动态规划法、分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子算法等一些智能算法。0-1背包问题一般描述为：给定n种物品和一个背包。物品i的重量是w(i)，其价值为v(i)，背包的容量为c。问应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。此问题的形式化描述是，给定cw，v，in，要求找出一个n0，i0i01nn（x，x，，x），x，inwxc，使得，而且vixiii元0-1向量12ni{0,1}1i1i1达到最大。n数学模型：maxvixii1n约束条件：wixic，xi{0,1},1ini1背包问题的求解算法蛮力算法（bruteforcemethod）基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为 n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值， 然后记录遍历过的最大价值。3v1.0 可编辑可修改代码实现:#include<iostream>#include<algorithm>usingnamespacestd;#defineN100<=C){for(intk=0;k<n;k++) X[k]=cx[k];;cp=cp+a[i].p;cx[i]=1; ;cp=cp-a[i].p;cx[i]=0; ,&a[i].p);b[i]=a[i];}intsum1=KnapSack1(n,a,C,X); vi wi vi wi ri vi wi4v1.0 可编辑可修改时，在步骤（3）中计算最优解时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。使用动态规划求解问题，最重要的就是确定动态规划3要素：（1）问题的阶段；（2）每个阶段的状态；（3）从前一个阶段转化后一个阶段之间的递推关系[4]。分析最优解的性质，刻画最优解的结构特征——最优子结构性质分析设（x1，x2，，xn）所给0-1背包问题的一个最优解，则（x2，x3 ，xn）是下面相应子问题的一个最优解：n目标函数：maxvixii2n约束条件：wixicw1x1,xi{0,1}(2in)i2证明：若（x2，x3 ，xn）不是上述子问题的一个最优解， 而（y2，y3，，yn）是他的nnn最优解。由此可知，viyivixi且w1x1wiyic。因此i2i2nnv1x1viy1vixii2i1nw1x1wiyici2这说明（x1，y2，，yn）是原问题的一个更优解，从而（y1，y2，，yn）不是所给原问题的最优解，产生矛盾。所以（x2，x3 ，xn）是上述子问题的一个最优解。递归关系由于0-1背包问题的解是用向量（x1，x2，，xn）来描述的。因此，该问题可以看做是决策一个 n元0-1向量（x1，x2，，xn）。对于任意一个分量 xi的决策是“决定xi=1或xi=0，i=1,2,⋯,n。对xi1决策后，序列(x1，x2，，xi1)已被确定，在决策xi时，问题处于下列两个状态之一：5v1.0 可编辑可修改（1）背包容量不足以装下物品 i，则=0，装入背包的价值不增加；（2）背包容量足以装入物品 i,则=1，装入背包的价值增加 vi。在这种情况下，装入背包的价值最大化应该是对决策后的价值。设所给0-1背包问题的子问题nmaxvkxkkin(0,1)，iknwkxkj，xkki的最优值为m(i,j), 即m(i,j) 是背包容量为 j，可选择的物品为 i,i+1, ⋯,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算（mi,j ）的递归式为：m(i,j)m(n,j)

max{m(i1,j),m(i1,jwi)vi}(jwi){m(i1,j)(0jw)ivn，jwn{0，0jwn算法设计基于上面的讨论，求解 0-1背包的动态规划算法步骤如下：步骤1：当wi(1in)为正整数时，用数组w[n]来存放n个物品的重量；数组v[n]来存放n个物品的价值，背包容量为c，数组M[n+1][c+1]来存放每一次迭代的执行结果；数组 x[n]用来存储所装入背包的物品状态；步骤2：初始化。数组 M的第0行第0列全部设置为0；步骤3：循环阶段。按式（5）确定前i个物品能够装入背包的情况下得到的最优值；步骤3-1：i=1时，求出M[1][j],1 ≤j≤c；步骤3-2：i=2时，求出M[2][j],1 ≤j≤c；6v1.0 可编辑可修改⋯⋯步骤3-n:i=n 时，求出M[n][c] 。此时，M[n][c]便是最优值；步骤4：确定装入背包的具体物品。从M[n][c]的值向前推，如果M[n][c]>M[n-1][c]，表明第n个物品被装入背包，则xn=1，前n-1个物品没有被装入背包，则xn=0，前n-1个物品被装入容量为 c的背包中。以此类推，知道确定第1个物品是否被装入背包为止。由此，得到下面的关系式：如果M[i][j]=M[i-1][j], 说明第i个物品没有被装入背包，则 xi=0；如果M[i][j]>M[i-1][j], 说明第i个物品被装入背包，则 xi=1，j=j- wi。按照上述关系式，从M[n][c]的值向前倒推，即j初始为c，i初始为n,即可确定装入背包的具体物品。上述算法需要O（nc）时间计算时间。不过上述算法有2个明显的确点。一是算法要求所给物品的重量wi（1≤i≤n）是整数；二是当背包容量c很大时，算法需要的计算时间较多。运行结果贪心算法求解0/1背包问题的时间复杂度为： O（nm）7v1.0 可编辑可修改回溯法（Backtracking ）回溯法0-1背包问题的实现回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是r为还未遍历的对象的收益之和，将r加到cp(当前节点所获收益)之上，若(r+cp)<=bestp(目前最优解的收益)，则不需搜索右子树。一种更有效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量。编程实现如下#include""#include<iostream>#include<algorithm>#include<>#include<>usingnamespacestd;#defineN100 <=W){ ;cp=cp+a[i].p;cx[a[i].sign]=1; ;cp=cp-a[i].p; ign]=0; ign=i;}sort(a,a+n,m); ;cout<<b[i].w<<"\t";8v1.0 可编辑可修改cout<<b[i].p<<endl;}}cout<<"放入背包的物品总重量为： "<<totalW;cout<<endl;cout<<"放入背包的物品总价值为： "<<bestP<<endl;}intmain()=rand()%1000;a[i].p=rand()%1000;b[i]=a[i];}cout<<"物品的重量和价值分别如下： "<<endl;for(inti=0;i<n;i++) ;cout<<"\t";cout<<a[i].p<<endl;}QueryPerformanceCounter(&begin);KnapSack3(n,a,W,X); 3运行结果9v1.0 可编辑可修改回溯法法的时间复杂度为分枝-限界法（Branch-thresholdmethod ）分枝-限界法的基本原理与分析分枝限界法是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对 E-结点的扩充方式。每个活结点有且仅有一次会变成 E-结点。当一个结点变为 E-结点时，则生成从该结点移动一步即可到达的所有新结点。 在生成的结点中，抛弃那些不可能导出最优解的结点，其余结点加人活结点表， 然后从表中选择一个结点作为下一个 E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。分枝限界0-1背包问题的实现首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中， 节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。 如果该左儿子结点是可行结点， 则将它加入到子集树和活结点优先队列中。 当前扩展结点的右儿子结点一定是可行结点， 仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。 当扩展到叶节点时为问题的最优值。10v1.0 可编辑可修改编程实现如下#include<iostream>#include<algorithm>usingnamespacestd;#defineN100 >H[i/2].b){swap(H[i],H[i/2]);}else{done=true;}i=i/2;}}}>H[i].b){i++;}if(H[i/2].b<H[i].b){swap(H[i/2],H[i]);}else{done=true;}}}}<=M)&&(i<n)){w+=a[i].w;;/a[i].w;}else{11v1.0 可编辑可修改node->b=p;}}}ign=i; ; ; ign]=1;}else{X[a[i].sign]=0;}}deletexnode;deleteheap;returnv; ,&a[i].p);b[i]=a[i];}intsum4=KnapSack4(n,a,C,X); 4运行结果分支限界法求解 0/1背包问题的时间复杂度为：12v1.0 可编辑可修改遗传算法（Geneticalgorithm ）遗传算法是模拟达尔文的生物自然选择学说和自然界的生物进化过程的一种自适应全局概率搜索算法[2]。它是由美国的教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和良好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定规则。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子）进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。算法设计遗传算法解决0-1背包问题的基本步骤如下：（1）群体的初始化：确定种群规模 M,交叉概率pc、变异概率pm、染色体长度N即最大进化代数 T。随机初始化染色体，给出物体体积、物品价值 v和背包容量c。（2）产生遗传编码：采用二进制n维矢量解X作为解空间参数的遗传编码，串的长度等于n,xi=1表示该物体装入背包，xi=0表示该物品没有被装入背包。（3）适应度函数的构造：适应度函数的建立是解决背包问题的关键。 首先背包问题的目标函数和约束条件文章前面已提出n数学模型：maxvixii113v1.0 可编辑可修改n约束条件：wixic，xi{0,1},1ini1现给出构造它的2种适应度函数：n(1)Fvixi,其中xi或（，）10i1,2,ni1nk(2)F(,其中k，其中xi或（，）vixi)1.0012510i1,2,ni1（4）选择操作：根据选择概率选择染色体，将上述的个体作为第一代，采用以正比于适应度的赌轮随机选择方式，每个个体适应度值为fi，则i被选中的n概率Pisfi/fi；对于初始化后的种群，先计算出每条染色体的适应度i1值，再计算出其被选择的概率，将它们进行比较，把选择概率最小的一条染色体淘汰掉，并选择概率最大的一条染色体进行复制，用这条复制的染色体代替淘汰的染色体的位置。（5）交叉操作：判断染色体是否为活的染色体，若为活的染色体，则将染色体进行交叉，一般采用一点交叉方式，交叉概率为Pc，具体操作是在个体串中随机设定一个交叉点，实行交叉时，该点前后的两个个体的部分结构进行互换，并生成两个新的个体。（6）变异操作：染色体变异采用位点变异的方式。位点变异比较简单，对于0-1背包问题来说，就是把染色体的变异位1变为0,0变为1，其他位保持不变。变异概率为Pm，变异的目的是使其变异后的适应度大于或等于其原适应度。先选择一个变异位进行变异，再计算它的适应度，看它是否大于或等于其原来的适应度，若不是的话就重新选择变异位进行变异操作。对种群依次进行选择、交叉、变异后就检验得到的新个体，当某代得到的结果满足要求或当前代数等于结束代数时算法结束得到结果，否则重新选择、交叉、变异操作，直到得到满意的结果为止。使用幂函数适应度函数的遗传算法全局搜索效率比较高 [2]。14v1.0 可编辑可修改算法分析与比较通过上面几种算法基本原理的介绍和分析，得到了不同方法解决NP难的0-1背包问题。下面从时间、空间复杂度、准确性等方面进行进一步的分析比较。动态规划算法的空间和时间复杂度由物品的数量和背包的承重量来决定。若物品数量为n,背包承重量为c,初始化数组需要空间为O（nc）,两重for循环时间复杂度为O(nc)。动态规划能够保证求解的正确性，但它速度慢，空间消耗大。贪心算法的时间复杂度为O(nlogn)。但贪心算法属于近似算法，速度快，时间消耗少，但不能确定结果为最优解，体现了该算法的局限性。遗传算法跟贪心算法一样，也是一种近似算法。它的时间复杂度取决于采用的适应度函数。第一种适应度函数对遗传算法的参数比较敏感，幂函数的适应度函数的遗传函数能获得高质量的解。算法的效率分析（1）蛮力法对于一个有n个元素的集合，其子集数量为2^n，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个2^n的算法（2）贪心法贪心算法总是作出在当前看来是最好的选择， 即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解， 但其最终结果却是最优解的很好近似解。贪心算法的时间复杂度为 O(nlogn）。（3）动态规划法从m(i，j)的递归式容易看出，算法 Knaspack需要 O(nc)计算时间;Traceback需O(n)计算时间；算法总体需要 O(nc)计算时间。（4）回溯法15v1.0 可编辑可修改由于计算上界函数需要O(n)时间，在最坏情况下有个右孩子结点需要上界函数，故计算0-1背包问题的回溯算法所需的计算时间复杂度为。对回溯法的改进主要是对判断是否移动右子树上，一种更有效的方法是按效益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放人背包的对象时，就使用它的一部分。回溯算法的运行时间取决于它在搜索过程中所生成的结点数,而限界函数可以大量减少所生成的结点个数,省去许多无谓的搜索,使得搜索速度更快,其调用限界函数计算上界需花费O(n)时间,最坏情况下有个结点需调用限界函数,需花费O(n)时间,所以该算法的时间复杂度为。分枝-限界法分支限界法求解0/1背包问题的时间复杂度为：为了直观表示，特将四种算法的时间复杂度总结如下：（1）为了更好地说明问题，现在对不同问题规模三种不同算法所需要的时间进行比较。随着问题规模的增大，各算法的计算时间都在增大，由于回溯法相对于其他算法所增加的时间更加显著，特此，单独考虑回溯法的情况。16v1.0 可编辑可修改（2）此种情况下背包的容量为 100，不同问题规模回溯法所用时间所下表所示由以上测试时间可以很好的验证，当背包容量和问题规模达到一定程度时，用回溯法解决背包问题，因此随着物件数 n的增大，其解的空间将以 级增长，当n大到一定程度上，用此算法解决背包问题将是不现实的。这正好与理论分析的情况是一致的。6从实验中也可以发现，当问题规模很小的时候，四种算法都有较好的稳定性，计算时间都相差不多。随着问题规模的增大，各算法的计算时间差别逐渐显现出来。7对比以上四种算法可以看出，各种算法都有自己的特点，贪心算法速度比较快，但是所得的解有时可能只是局部最优解；分枝限界法需要 的解空间。故该算法不常用在背包问题求解；回溯法比分枝限界在占用内存方面具有优势。回溯法占用的内存是0(解空间的最大路径长度)，而分枝限界所占用的内存为0(解空间大小)。对于一个子集空间，回溯法需要0(n)的内存空间，而分枝限界则需要的空间。虽然最大