背包问题的若干算法研究

节蒂肁莈薀蒁螀膁蒆蒁袃莆莂薀羅腿芈蕿肇羂薇薈袇膇薃薇罿肀葿薆肂芆莅薅螁肈芁薅袃芄蕿薄羆肇蒅蚃肈节莁蚂螈肅芇蚁羀芀芃蚀肂膃薂虿螂荿蒈虿袄膂莄蚈羇莇芀蚇聿膀蕿螆蝿羃蒄螅袁膈莀螄肃羁莆螃螃芆节螃袅聿薁螂羇芅

背包问题的若干算法研究 摘要 本文主要通过若干算法来求解背包问题，同时比较各种算法的时间复 【】 杂度等性能的比较。 关键词 ; 背包问题；贪心算法；遗传算法；动态规划量子算法 【】 1 问题描述 0-1 背包问题： niWiVi 给定种物品和一个背包。物品的重量是，其价值为，背包的容 C? 量为。应如何选择装入背包的物品，使得装入背包中物品的总价值最大在选择装入背 (1)(0) i2i 包的物品时，对每种物品只有种选择，即装入背包或不装入背包。不能将物品 i 装入背包多次，也不能只装入部分的物品。 i 背包问题：可以选择物品 0-1i 与背包问题类似，所不同的是在选择物品装入背包时， 的一部分 1≤i≤n ，而不一定要全部装入背包，。 ni wi 背包问题可以描述为如下：假定有个物体和一个背包，物体的质量为，价值为 piMixi1<=i<=n,0<=xi<=1) ，而背包的容量为。若将物体的一部分（装入背包中，则有 pi*xiw1*x1+w2*x2+…………+wn*xn)<=M 价值。在约束条件（下使目标 (p1*x1+p2*x2+……+pn*xn)0<=xi<=1,pi>0,1<=i<=n. 达到极大，此时满足 20-1 ．贪心算法求解背包问题 贪心算法是一种改进了的分级处理算法，它每次都一步一步的进行，根据某 个优化目标保证每一步的局部最有解最优。贪心算法是从局部最优出发，最终得 到整体最优，也就是结果最优。贪心算法每次只考虑一步，每一步数据的选取都 必须满足局部最优条件。枚举剩下的数据与当前已经选取的数据组合获得的解中， 提取其中能获得最优解的唯一的一个数据，加入结果集合中，直到剩下的数据不 能再加入为止。对于一个问题只能用穷举法求解的问题，用贪心法求解能够获得 问题次优解，此时贪心算法也是比较好的算法。 1） 用贪心算法求解背包问题的策略 (1) 价值贪婪优先策略：从剩余的物品中，选取价值最大的可以装入背包的物 品。此时，价值最大的优先被装入背包，然后装入下一个价值最大的物品，