本科-毕业论文---背包问题Word文件下载.doc

1、摘要：背包问题是一种组合优化的NP完全问题。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。传统求解该问题的方法可以概括为精确算法和近似算法， 近年来利用近似算法求解背包问题成为重点。本文总结了背包问题的定义和性质，给出了背包问题不同的算法以及各算法的思想综述。关键词: 动态规划算法；贪婪算法；遗传算法；蚂蚁算法；回溯法。Knapsack problem algorithm thought summaryAbstract:The Knapsack problem is the NP complete questi

2、on which one kind of combination optimizes. How does the question name originate from chooses the most appropriate goods to lay aside in assigning in the knapsack. The similar question appears frequently in the trade, the combinatorics, domains and so on computation complex theory, cryptology and ap

3、plied mathematics. The tradition solves this question the method to be possible to summarize for the precise algorithm and the approximate method, in recent years used the approximate method solution knapsack question to become key. This article summarized the knapsack question definition and the na

4、ture, has given the knapsack question different algorithm as well as various algorithms thought summary. Keywords: Dynamic programming algorithm; Greedy algorithm; Genetic algorithm; Ant algorithm; Backtracking. 前言 背包问题是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包

5、中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际的观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等，都是典型的应用例子。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。然而当问题的规模较大时，得到最优解是极其困难的。算法是一系列解决问题的清晰指令, 一个算法的优劣可以用空间复杂度与时间复杂度

6、来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、 粒子群算法、蚁群算法等,由于精确算法的时间复杂性和空间复杂性等缺点， 近年来利用近似算法求解背包问题成为重点。本文主要研究背包问题的总体概况，整理了背包问题的定义、性质、算法技巧等，对各个算法思想进行概括总结，并对各种算法的复杂度进行分析。1背包问题的概念及算法分析1.1背包问题的定义我们有n种物品，物品j的重量为

7、wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：maximize subject to 如果限定物品j最多只能选择bj个，则问题称为有界背包问题。如果不限定每种物品的数量，则问题称为无界背包问题。1.2背包问题算法分析根据背包问题定义，可以将其转化为如下的约束条件和目标函数：于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量。首先说明一下0-1背包问题拥有最优解。假设是所给的问题的一个最优解，则是下面问题的一个最优解：。如果不是的话，设是这个问题

8、的一个最优解，则，且。因此，这说明是所给的0-1背包问题比更优的解，从而与假设矛盾。背包问题是算法设计分析中的经典问题。目前, 随着计算机算法的不断发展, 涌现出大量可用于解决背包问题的算法和思想, 背包问题的建模与求解有着广泛的应用前景。其求解方法主要有三类：第一类是精确方法, 如动态规划、回溯法和分枝一限界法等 第二类是近似方法,启发式算法, 如贪心算法。第三类是全局优化方法, 如遗传算法、蚁群算法、遗传退火进化算法等。下面将对这三类求解方法进行分析和比较。2精确算法2.1动态规划法动态规划的基本思想:将一个比较大的问题逐层分解成相对比较小的问题,这些较小的问题一般都可以解决,在这一点与上

9、面提到的贪心算法和分治法很类似,但是动态规划算法有着自身的特点,解决了分治法中相同子问题重复求解的问题。贪心算法要求找出问题的最佳量度标准,而在现实问题中往往很难找到最佳量度标准,对我们的动态规划法来说,利用了最优子结构, 由下向上的方法从子问题的最优解一步一步地构造出整个问题的最优解。有时动态规划法可以解决贪心算法不能解决的问题。动态规划算法的每一步决策都是根据前一步的状态参量来决定这一步状态参量的设置,也就是说,从初始状态到最终状态要经过多个过程, 经历不同的状态, 不断地根据上一步状态决定下一状态,从而形成了一个决策序列, 最终将整个问题解决,这就是典型的多段决策的特性。由上面的动态规划

10、法的介绍,可以看出0 /1背包问题,是符合多段决策的特点和具有重叠子问题。因此,在设计0 /1背包问题解决方案时, 可以将整个物品放到背包的过程,看成一个取物品的过程。可以当背包容量为x时,第i个物品导致的最优解为fi （ x） ,显然, fi （M ）为整个问题的最优解,M为背包的最大容量, 根据动态规划的算法思想, 可以得到如下递归方程:fi （ x） =max fi - 1 （ x） , fi - 1 （ x - wi ） + pi 其中i代表第i次决策, 0 fi - 1 （ x- wi ） +wi ,则fi = fi - 1 （ x）表示物品i不装入背包的效益比装入还要大, 反之fi

11、 = fi - 1 （ x - wi ） + pi , 可见,第i个物品是否装入背包就取决于fi - 1 （ x）和fi - 1 （ x - wi ） + pi 的大小的过程。下面对动态规划的算法进行一下相应的算法分析,首先是时间复杂度, 从上面算法的执行过程中可以看出假设有Q （ n）个子问题,每一个子问题最多需要m 次决策, 则计算的频率为nm, 回溯的频率为n,那么整个过程的算法的时间复杂度为T（ n） = nm + n, 即为Q （ nm ） 。然后, 我们在看一下另一个考察指标空间复杂度,根据上面的得到的计算频率和回溯频率,根据空间复杂度计算的原则可知为Q （ n） 。从上面的分析可

12、以看出动态规划法的时间复杂度和空间复杂度均成直线增长。在整个计算过程中,选择一种行之有效的决策方法是至关重要的,能够分解成比较容易解决的子问题, 是决策设计的最佳标准。2.2回溯法回溯其实就是穷举，穷举所有的解，找出解中最优的值。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。回溯算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法

13、在求解空间树时，只要其左儿子节点时一个可行结点时就进行该左子树，只有右子树包含可行解时才进入右子树，否则就剪去右子树。 回溯法的基本思路是：确定解空间，建立解空间树，用深度优先搜索算法递归搜索解空间树，并同时注意剪枝。 背包问题的算法思路：按照物品的单位价值从大到小排序，计算当前节点的上界，搜索左子树，如果右子树包含可行解，就搜索右子树。剪去右子树条件：当前价值加上剩余物品的总价值小于当前的最优总价值时，不需搜索右子树，可将右子树剪去。用回溯法求解背包问题的伪代码：void Backtrack（int i）如果已经搜索完一条从根节点到叶节点的路径，更新当前解的最优值bestp；如果左节点的重量

14、小于剩余的背包重量，进入左子树进行搜索；如果右子树包含当前解，进入右子树进行搜索。否则剪去右子树。回溯法实际时穷举算法，用一定的剪枝进行优化，算法的时间复杂度为O（n*2n），n为物品个数。3启发式算法31贪心算法贪婪算法是一种逐步构造最优解的启发式算法， 其基本思想是在每一阶段它都在一定的规则下构造出当前看似最优的一个决策，决策一旦做出就不再更改。贪婪算法常以当前情况为基础作最优选择，而不考虑整体情况，所以贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。虽然这种启发式的策略并不一定能够获得最优解,然而在许多情况下确能达到预期的目的。贪婪算法解决优化问

15、题的最关键问题是制定贪婪策略。对于背包问题来说，贪婪的策略有常用的3种。它们是价值贪婪准则、质量贪婪准则和价值密度贪婪准则。每种贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。其中采用价值密度（价值重量比 pi/ci）的贪婪准则是从剩余物品中选择可以放入背包的 pi/ci值最大的物品，直到超出背包容量限制装不下为止，并将未装入背包的物品编码修正为 0。算法的时间复杂度为 o（nlogn）。这种策略对于连续背包问题可保证得到最优解，但对于 01背包问题不一定能得到最优解。因此出现了一些对于贪婪算法的改进方法，例如文献中提出的算法在不增加时间复杂度的基础上，

16、 保证求解质量较稳定地优于价值密度贪婪算法及价值密度改进算法。近年来还产生了贪婪法与其他算法结合的混合算法，有赵新超，杨婷婷提出的更贪心粒子群算法 , 该算法对超过背包重量限制的粒子的处理方法是去掉已经装进去且性价比最差的物品，直到满足重量约束条件为止，这样在改善粒子质量的同时避免了罚函数方法中敏感的参数选择问题； 对于可行粒子的处理措施是将还未装入背包且性价比最好的物品装进背包，直到不能装为止。结果表明更贪心粒子群算法无论在寻优能力、计算速度和稳定性方面都有很好的表现，非常适合于求解大规模背包问题。还有刘茜、马杰良提出的混合遗传算法，它针对遗传操作交叉和变异的过程中不符合约束条件的个体，在解

17、码过程中引入贪婪算法优先装入价值重量比大且物品标记为1 的物品， 直至背包容量限制装不下为止，通过引进贪婪算法使得遗传进化过程以良好的种子为基础进行，此外算法在变异操作和进化终止条件的设计上也进行了改进， 结果表明该算法在解的质量和求解速度方面都比遗传算法有很大的改良。贪婪算法通过一系列的选择得到问题的解，在每一次总是做出在当前状态下看来是最好的选择，也就是希望通过局部的最优来达到一个全局的最优。这种启发式的策略并不总能获得最优解，然而在许多情况下确能达到预期的目的，而且对于很多NP 问题来说，本身就不存在最优解。对于01 背包问题来说，贪婪的策略有常用的3 种。第一种贪婪准则：从剩余的物品中

18、，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。第二种贪婪准则：从剩下的物品中选择可装入背包的重量最小的物品，如此继续下去直到不能满足条件为止。第三种贪婪准则：价值密度（价值重量比pi wi）贪婪算法，这种选择准则为： 从剩余物品中选择可装入包的pi wi值最大的物品，这也是本文所选择的贪婪策略，因为它是一个直觉上近似的解。用贪婪算法求解01 背包问题的过程如下：对于给定的物品，分别求出价值密度（价值重量比），ripi wi，i1，2，n；忽略先前的物品排序， 按照价值密度， 进行非升序排列：（p（1）/w

19、（1）（p（2）/w（2）（p（n）/w（n）；重复以下步骤，直到不满足条件为止：对于当前的物品，如果重量小于包中剩余的容量，则放入，并置物品标志为1（表明被选中），否则就停止。算法主要耗时是在于将各种物品按价值密度大小排序，本文利用MATLAB 软件中的SORTROWS 函数进行排序，此函数是基于快速排序（quicksort）实现的，因此，算法的时间复杂度为O（nlogn）。4全局优化方法4.1遗传算法遗传算法是计算数学中用于解决最优化的搜索算法，是一种进化算法。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。通常解用二进制0和1表示，进化从一个

20、个体发生，然后一代一代发生。在每一代中，该种群的价值被评估，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。遗传算法的一般步骤：确定二进制编码取值范围，初始化染色体的个数，并随机产生所有的染色体，构造评价函数和个体的适应度总和，经过交叉运算和变异操作，进行遗传迭代求解。01背包问题的遗传算法求解策略：（1）二进制法策略：将物品根据单位重量价值从大到小排序。用0和1分别表示物品i放入背包和物品i不放入背包，如果Xi表示物品i是否放入背包，则放入背包的总重量为w=w1*x1+w2*x2+wn*xn;放入背包的物品的总价

21、值为P=p1*x1+p2*x2+pn*xn。Fm存放目标函数值就是个体的适应度。Tn存放每个个体的约束条件值1） 初始种群产生，并计算每个适应度值和其对应的约束条件值（即为染色体中选取的物品的重量），比较初始种群中各个个体的适应度。选择最大者所对就的个体作为第一代最优个体并记录该个体以及它的适应度和约束条件值。2） 计算每个个体的选择概率PiFi/E（Fi）3） 根据轮盘睹法进行个体选择；4） 进行交叉运算，随即选择一对个体产生一对有效交叉位置进行交叉运算，并计算新产生的个体的适应度值和约束条件值,如果新产生的个体重量大于背包容量，则对新产生的这个个体进行修正，放弃在一个个体中的一个物品，增加

22、另一个个体的一个物品使其重量小于背包重量。5） 进行变异操作，如果一个个体的一个基因为1，则变为0，如果使0则变为1，重新计算该个体的适应度和约束值。6） 选取具有最大值的适应度个体，如果其适应度大于当前的最优值的适应度，则更新当前的最优值为选取的个体，更新当前最优值的约束条件和迭代次数。7） 循环迭代直到迭代次数超过设定最大值。算法的时间复杂度为O（N*n2）N为迭代次数，n为物品个数4.2蚁群算法蚁群算法是由意大利学者 Dorigo M.等提出的一类模拟蚂蚁群体觅食行为的仿生优化算法。算法的基本思想是蚂蚁将根据信息素的多少选择走哪一条路，蚂蚁在觅食过程中会留下一种称为信息素的物质，若蚂蚁从

23、巢穴到食物源所走的路径较短，则该蚂蚁从巢穴到食物源后再返回巢穴的时间也就较短，这样同时间内在较短路径上蚂蚁分泌的信息素就会较多。后面的蚂蚁将根据其他蚂蚁留下来信息素的多少而选择路径，某一条路径上的信息素越多，则这条路径被选择的概率越大。蚂蚁群体的这种集体行为构成了一种学习信息的正反馈机制，蚂蚁之间通过信息素来交流信息。蚁群算法模拟了这种优化机制，通过个体之间的信息交流与协作来寻找最优解。蚁群算法现已成功运用在 TSP、图像处理、车辆路径系统、通信系统等领域。它具有较强的鲁棒性、分布性、全局优化性和易与其它优化算法融合的优点,现已是解决 NP-hard问题的一个有效工具。 蚁群算法解决 0/1

24、背包问题的核心是：在某一物品上聚集的信息素越多，则该物品被选择的概率就越大。背包问题的蚁群算法求解过程是：设置迭代次数；将各蚂蚁置于相应变量的 0、1位置点； 按转移概率移动各蚂蚁； 按强度更新方程更新信息素轨迹； 记录当前最佳蚂蚁位置； 返回步骤循环直到满足退出条件。 就蚁群算法而言当处理的数据比较小时其具有很快的收敛速度， 而随着数据规模的增大算法的收敛速度明显降低。蚁群算法在减少寻优计算量和缩短算法运行时间方面，有待进一步改进。针对蚁群算法的缺点，许多学者对蚁群算法进行了改进。 赵朝卿，胡小兵等提出了一种求解 0-1背包问题的混合型算法（KPAICACA），先利用蚁群算法求优化解，然后利

25、用抗体克隆选择算法扩大解的搜索空间，使得在收敛速度和寻优能力两方面都有明显改善。具体方法是：每个物品 i的属性有重量 ci，价值 pi和信息素 i，即信息素积累在物品上。选择物品 i的期望度为 i=pi/ci。每只蚂蚁都附一个背包和一个禁忌表， 蚂蚁将根据选中物品的重量来决定是否将其装入背包。 若物品装入背包而不超过其容量，则继续选择下一个物品；否则将其编号放入禁忌表中，以后选择物品时不再考虑。经过 n次选择，构建了一个由物品编号表示的解，当 m 只蚂蚁都构建了自己的解，将这些编号解变换为 0-1 序列解，每个序列解被视做一个抗体，抗体编码的长度为 n，抗体群的规模等于蚂蚁种群的规模 m。随后

26、对抗体群进行克隆、变异和选择操作。抗体免疫克隆算法搜索完成后，根据背包中物品的价值总和 P，记录最优解以及对应的物品价值总和，并对物品上的信息素进行更新。 43 量子算法求解背包问题 量子算法从概率算法出发，系统由一个状态转移到另一个状态有一个状态几率矢量，通过状态几率矢量和状态转移矩阵得到下一个状态。长度为 的量子字节串A1n在 1-n中Ai=Xi （xi （O，1 ）则 A显然有N2 种状态用量子算法求解背包问题的步骤如下：1.给定常数c，井随机选取A的种状态在种状态中选择最大的Y=Ai*Pi.且 2. 重复下列操作 c次2.1对2n个状态给定初始几率幅均为（,-,）,并将y绑定在一起，满

27、足1条件的做标记。2.2.1给定常数m=1并且r=6/5 2.2.2随机选取非负整数 jy且重量小于背包重量，则y状态的值改为y1退出 2.2. 2.2.6否则 mmin（r,），goto 2.2.2 3得到最优解 Y量子算法的时间复杂度为O（C*2n）c为重复的次数。4.4 模拟退火算法1983 年，Kirkpatric 等将热力学中的退火思想引入组合优化领域，提出了一种解大规模组合优化问题，特别是NP 完全组合优化问题的有效近似算法模拟退火算法。它源于对固体退火过程的模拟，使算法在多项式时间内给出一个近似最优解。模拟退火算法是模仿固体物质的退火过程。高温物质降温时其内能随之下降，如果降温过程充分缓慢，则在降温过程中物质体系始终处于平衡状态，反之降温太快，则降到同一低温时会保持内能。用模拟退火算法求解01 背包问题的过程如下：（1）解空间S由于模拟退火算法已经证明，最后的最优解并不太依赖初始解的选取，所以在这里可任选一初始解，本文初始解为（0，0，0）1n。（2）目标函数。最大价值的目标函数为：（3）新解的产生。随机选取物品，若i 不在背包中，则将其直接放入背包中，或同时从背包中随机取出另一物品j；若i 已在背包中，则将其取出，并同时随机装入另一