背包问题的算法研究与实现本科.doc

《背包问题的算法研究与实现本科.doc》由会员分享，可在线阅读，更多相关《背包问题的算法研究与实现本科.doc（28页珍藏版）》请在三一文库上搜索。

1、华中师范大学汉口分校华中师范大学汉口分校 本本 科科 毕毕 业业 论论 文文 0-10-1 背包问题的算法研究与实现背包问题的算法研究与实现 院院 系：系：信息科学技术学院信息科学技术学院 专专 业：业：计算机科学与技术计算机科学与技术 年年 级：级： 20052005 级级 学学 生：生： 刘念刘念 学学 号：号： 20059110322005911032 指导老师：指导老师： 宾云峰、杨健宾云峰、杨健 华中师范大学汉口分校 学位论文原创性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下独立进行研究工作 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集

2、体已经发表或撰写的成果作品。本人完全意识到本声明的法律后 果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位学位论论文版文版权权使用授使用授权书权书 本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校 保留并向有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。 本学位论文属于 1、保密 ，在_年解密后适用本授权书。 2、不保密 。 （请在以上相应方框内打“” ） 学位论文作者签名： 日期： 年 月

3、日 导师签名： 日期： 年 月 日 3 目目 录录 内容摘要1 关 键 词1 ABSTRACT2 KEY WORDS.2 1 绪论3 1.1 问题的提出及研究意义 3 1.2 0-1 背包问题的算法研究的分析.3 1.3 课题的主要研究内容 4 2 0-1 背包问题的实现 5 2.1 0-1 背包问题在动态规划中的实现.5 2.2 0-1 背包问题在回溯法中的实现.8 2.3 0-1 背包问题在分枝-限界法中的实现.12 2.4 0-1 背包问题在遗传算法中的实现16 3 解 0-1 背包问题的算法比较与分析.20 4 总结与展望 .22 参考文献.23 致 谢.25 1 内容摘要内容摘要：背

4、包问题是一个在运筹学领域里常见的典型 NP-C 难题，也是算 法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在 实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对 该问题的探索和应用研究一直在进行。在先进理论指导下，求解 0-1 背包问题 具有科学、高效、经济、灵活、方便等显著特点。 那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题 的解，就要先设计出算法,本文采用动态规划法，回溯法，分枝-限界法，遗传 算法四种方法分别对背包问题、0-1 背包问题及简单 0-1 背包问题进行算法设 计和时间复杂度分析，给出具体算法设计和实现过程。并以具体

5、实例详细描述 不同方法求解问题解时算法基本思想，然后就解决 0-1 背包问题对这四种算法 进行详细的比较，总结四种方法实现的优缺点并得出结论。如何将背包问题应 用于实际问题中，有针对性地设计适合求解实际 0-1 背包问题的算法，并很好 地解决实际问题，是计算机工作者不断思索、研究的一个领域。 关关 键键 词词：0-1 背包 动态规划 回溯法 分枝-限界法 遗传算法 2 AbstractAbstract： Knapsack problem is a typical NP-C problem as well as algorithm design and analysis of the class

6、ical problems in the common field of operations research. It is very important to study the solution of the problem, whether in theory or in practice. After some research, a lot of classical methods solving this problem have been come up with ,and the exploration of this issue and applied research h

7、as been ongoing. Under the guidance of advanced theory, there are distinctive features such as scientific, efficient, economic, flexible and convenient features in solving the 0-1 knapsack problem . So to solve the knapsack problem, the first premise is to design a good algorithm.To seek the solutio

8、n of knapsack problem, it is necessary to design algorithms using dynamic programming at first. In this paper, four methods such as dynamic programming, backtracking, branch - Bound method and genetic algorithm respectively aiming at knapsack problem ,0-1 knapsack problem and a simple 0-1 knapsack p

9、roblem carry out the algorithm design and analysis of time complexity, and give the specific algorithm design and implementation of the process.And descript detailedly the basic idea of algorithm by using specific examples in solving the issue with different ways .And then aiming at solving the 0-1

10、knapsack problem , compare four algorithms in detail and summarize the advantages and disadvantages of realization of four methods and reach a conclusion.How to apply the knapsack problem into the practical, and to design targeted for the practical algorithms of solving 0-1 Knapsack Problem and to s

11、olve the practical problems very well, is an area of computer workers constantly thinking and study. KeyKey wordswords：0-1 knapsack problem dynamic programmi backtracking branch - Bound method genetic algorithm 3 1 1 绪论绪论 1.11.1 问题的提出及研究意义问题的提出及研究意义 0-1 背包问题是计算机科学中的一个非常经典的优化问题。也是被证明了 的 NP 难度问题。它是在 1

12、978 年由 Merkel 和 Hellman 提出的。它的主要思路 是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将 它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的 物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量， 而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问 题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制 均被破译了，因此现在很少有人使用它。围绕这个问题的求解方法很多，比如 贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见 的一种求解方法。 多年来，背包问题吸引

13、了许多理论和实际工作者对此问题作深入的研究， 在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应 用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、 存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很 好地解决实际问题，是计算机工作者不断思索、研究的一个领域。 1.21.2 0-10-1 背包问题的算法研究的分析背包问题的算法研究的分析 0-1 背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关 问题的尽可能高效的算法并程序实现，而且能够分析算法的复杂性，通过实验 进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高

14、算 法设计与分析的应用能力。 0-1 背包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是 由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高 的理论研究价值，而且由于它是许多实际工程应用问题的种通用化描述，在很 多实际问题当中有着非常广泛的应用背景，例如项目决策等。他是最基本的背 包问题，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的 4 情况。它包含了背包问题中设计状态、方程的最基本思想，在经济管理、资源 分配、投资决策、装载设计等领域有着重要的应用价值。在计算理论中属于 NP-C 完全问题，其计算复杂度，传统上采用动态规划来求解。背包问题就是在

15、资源有限的条件下，追求总的最大收益的资源有效分配问题。 1.31.3 课题的主要研究内容课题的主要研究内容 1.3.11.3.1 背包问题的描述背包问题的描述 背包问题是整数规划中的一类特殊问题，在现实生活中具有广泛应用。如 果能提出求解此问题的有效算法，则具有很好的经济价值和决策价值。 问题的一般描述是：旅行者背包登山，背包的最大承重为 M，现有 n 个物 品可供选择装入背包，第 i 个物品莺量为 wi，价值为 pi，假定物品 i 的一部分 xi(0xi1)放人背包，获得价值为 xipi，由于背包最大承重为 M，要求装入物 品总质量不过超过 M，问旅行者应该如何选择物品装入背包，使得装入物品

16、的 价值总和达到最大值。 背包问题的数学描述如下：要求找到一个 n 元向量(x1，x2xn)，在满足 约束条件：情况下，使得目标函数，其中， 10 i ii x Mwx p x i i max 1in；M0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使 得目标函数达到最大的那个可行解则为最优解1。 1.3.21.3.2 0-10-1 背包问题背包问题 0-1 背包问题的提出 给定 n 种物品和 1 个背包。物品 i 的重量是 wi，其价值为 pi，背包的容 量为 M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在 选择装人背包的物品时，对每种物品 i 只有两种选择，

17、即装入背包、不装入背 包。不能将物品 i 装人背包多次，也不能只装入部分的物品 i。该问题称为 0- 1 背包问题。 问题符号化 0-1 背包问题的符号化表示是，给定 M0， w i 0， pi 0，1in ， 要求找到一个 n 元 0-1 向量向量(x1，x2xn)， X i =0 或 1 , 1in, 使得 5 ，而且达到最大2。Mwx ii px i i 2 2 0-10-1 背包问题的实现背包问题的实现 2.12.1 0-10-1 背包问题在动态规划中的实现背包问题在动态规划中的实现 2.1.12.1.1 动态规划的基本原理与分析动态规划的基本原理与分析 动态规划算法的基本思想是将待求

18、解问题分解成若干个子问题，先求解子 问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往 不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解 决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计 算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子 问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可 能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算 量，最后一个子问题的解即为问题解。采用此方法求解 0-1 背包问题的主要步 骤如下： 分析最优解的结构：最有子结构性质； 建立递归方程； 计算最

19、优值； 构造最优解4。 动态规划算法的每一步决策都是根据前一步的状态参量来决定这一步状态 参量的设置，也就是说，从初始状态到最终状态要经过多个过程，经历不同的 状态，不断地根据上一步状态决定下一状态，从而形成了一个决策序列，最终 将整个问题解决，这就是典型的多段决策的特性。 由上面的动态规划法的介绍，可以看出 0-1 背包问题，是符合多段决策的 特点和具有重叠子问题。因此，在设计 0-1 背包问题解决方案时，可以将整个 物品放到背包的过程，看成一个取物品的过程。 2.2.22.2.2 0-10-1 背包问题的实现背包问题的实现 最优子结构性质 0-1 背包问题具有最优子结构性质。设(y1，y2

20、yn)是所给 0-1 背包问题 的一个最优解，则(y2，y3yn)是下面相应子问题的一个最优解： 6 n ik kkx vmax nkix jxw k n ik kk ,1 , 0 因若不然，设(z2，z3zn)是上述问题的一个最优解，而(y2，y3yn)不 是它的最优解，由此可见,且c。因此 n i 2 n i iiy v 2 n i iiz w 2 w1y1 n i iiz v 2 v1y1 n i iiy v 1 c n i iiz w 2 w1y1 这说明(y1，z2zn)是所给 0-1 背包问题的一个更优解，从而(y1，y2yn)不 是所给 0-1 背包问题的最优解。此为矛盾1。 递

21、归关系 设所给 0-1 背包问题的子问题 n ik kkx vmax nkix jxw k n ik kk ,1 , 0 的最优值为 m(i,j)，即 m(i,j)是背包容量为 j，可选择物品为 i，i+1，n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性 质，可以建立计算 m(i,j)的递归式如下： wjjjim wijviwijimjim 0), 1( ,), 1(),),1(max j)m(i, wnj wnvnj 0 j)m(n, 7 算法描述 基于以上讨论，当 wi(1 i n)为正整数时，用二维数组 m来存储 m(i,j)的相应值，可设计解 0-1 背包问题的动

22、态规划算法 Knapsack 入下： template void Knapsack(Type v,int w,int c,int n,Type* * m) int jMax=min(wn-1,c); for (int j=0;j1;i-) jMax=min(wi-1,c); for (int j=0;j=w1) m1c=max(m1c,m2c-w1+v1); template void Traceback(Type* * m,int w,int c,int n,int x) for (int i=1;i class Knap friend Typep Knapsack(Typep*,Typew

23、*,Typew,int); private： Typep Bound(int i); void Backtrack(int i); Typew c; /背包容量 int n; /物品数 Typew*w; /物品重量数组 Typep*p; /物品价值数组 Typew cw; /当前重量 Typep cp; /当前价值 Typep bestp; /当前最优价值 ; template void knap:Backtrack(int i) if(in)/到达叶结点 bestp=cp; return; if(cw+wibestp) /进入右子数 Backtrack(i+1); template Type

24、p Knap:Bound(int i) /计算上界 Typew cleft=c-cw; /剩余容量 Typep b=cp; /以物品单位重量价值递减序装入物品 while (i=a.d); private: int ID; float d; ; template Typep Knapsack(Typep p, Typep w,Typew c,int n) 11 /为 Knap:Backtrack 初始化 Typew W=0; Typep P=0; Object*Q=new Objectn; for(int i=1;iK; K.p=new Typepn+1; K.w=new Typewn+1;

25、for (int i=1;i=a.d); private: int ID; float d;/单位重量价值 ; template class Knap; class bbnode 14 friend Knap; friend int Knapsack(int *,int *,int,int,int *); private: bbnode *parent; /指向父结点的指针 bool LChild; /左儿子结点标志 ; template class HeapNode friend Knap; public: operator Typep () const return uprofit; pr

26、ivate: Typep uprofit, /结点的价值上界 profit; /结点所相应的价值 Typew weight; /结点所相应的重量 int level; /活结点在子集树中所处的层序号 bbnode *ptr; /指向活结点在子集树中相应结点的指针 ； template class Knap friend Typep Knapsack(Typep *,Typew *,Typew,int,int *); public: Typep MaxKnapsack(); private: MaxHeap*H; Typep Bound(int i); void addLiveNode(Type

27、p up,Typep cp,Typep cw,bool ch,int level); bbnode *E; /指向扩展结点的指针 15 Typew c; /背包容量 int n; /物品总数 Typew *w; /物品重量数组 Typep *p; /物品价值数组 Typew cw; /当前装包重量 Typep cp; /当前装包价值 int * bestx; /最优解 ; template Typep Knap:MaxKnapsack() /优先队列式分支限界法，返回最大价值，bestx 返回最优解 /定义最大堆的容量为 1000 H=new MaxHeap(1000); /为 bestx 分

28、配存储空间 bestx=new intn+1; /初始化 int i=1; E=0; cw =cp =0; Typep bestp =0; /当前最优值 Typep up =Bound(1); /价值上界 /搜索子集空间树 while(i!=n+1)/ 非叶结点 /检查当前扩展结点的左儿子结点 Typew wt =cw +wi; if(wtbestp)bestp=cp+pi; AddliveNode(up,cp+pi,cw+wi,ture,i+1); up =Bound(i+1); /检查当前扩展结点的右儿子结点 16 if(up=bestp)/右子树可能含最优解 AddLiveNode(up

29、,cp,cw,false,i+1); /取下一扩展结点 HeapNodeN; H-deleteMax(N); E=N.ptr; cw=N.weight; cp=N.profit; up=N.uprofit; i=N.level; /构造当前最优解 for(int j=n;j0;j-) bestxj=E-LChild; E=E-parent; return cp; 1 2.42.4 0-10-1 背包问题在遗传算法中的实现背包问题在遗传算法中的实现 2.4.12.4.1 遗传算法的基本原理与分析遗传算法的基本原理与分析 遗传算法作为一种解决复杂问题的有效方法是在 1975 年首次由美国密西 根大

30、学的 Hol-land 教授和他的同事们借鉴生物界自然选择和进化机制基础之 上提出的，它是基于生物进化中自然选择、适者生存和物种遗传思想的一种搜 索算法。它将问题的每一个可能解看作是群体中的一个个体(染色体)，并将每 一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给 出一个适应值。算法将根据适应值进行寻优过程。遗传算法的寻优过程是通过 选择、杂交和变异等遗传算子来具体实现的，它的搜索能力由选择算子和杂交 算子决定，变异算子则保证了算法能够搜索到问题空间的每一个点，从而使其 具有搜索全局最优的能力。遗传算法的高效性和强壮性可由 Holland 提出的模 17 式定理和隐式并行

31、性得以解释。在遗传算法中，定义长度较短、低阶且适应值 超过平均适应值的模式在群体中数目的期望值按指数递增，这个结论成为遗传 算法的基本定理。 遗传算法可看成是在一个定义域为 L 维的向量空问 B。中有一适应度函数， 依其适应度大小，随机进行选择、交叉和变异操作来求此函数的最大值，即将 遗传算法看成是在某个空间进行求最大值的搜索技术。在操作中，新点主要是 由交叉操作产生。传统的交叉算子是随机操作，后代简单地继承了“父母”的 一部分基因，并不能保证子代的性能优于父辈，而且以这种方式点对点的搜索 范围有限，可能会忽略邻域内更好的点而使结果收敛于局部最优。 2.4.22.4.2 0-10-1 背包问题

32、的实现背包问题的实现 (1) 编码方案: 用遗传算法来求解 0-1 背包问题，一种很自然的编码方案 是将待求解的各量 X 表示成长为 n 的二进制字符串 Xi,j=1,2,n,xi=1 表 示物体 j 放人背包，xj表示物体 j 放入背包。 (2) 适应度函数的设计: 基于上述编码，按照所提出的罚函数 处理约束条 件的方法构造背包问题的适应度函数 (X):(X)=- = 1 () 这里，对于所有满足条C 的可行解 X，惩罚函数 Va(X)=0 = 1 惩罚函数可以使用对数函数，线性函数，二次函数等，分别随侵犯的程度增加 而顺序采用。 (3) 选择操作：根据选择概率选择染色体，将上述的个体作为第

33、 0 代。对 于每个染色体，计算累积概率 Qi，从区间(0, Qi) 种产生一个随机数 r，若 Qi -1=best then exit; sn为前 n 个物品的重量和 if kwk then search(k+1,v-wk); search(k+1,v); end; end; l DP Fi,j为前 i 个物品中选择若干个放入使其体积正好为 j 的标志，为 布尔型。 实现: A:将最优化问题转化为判定性问题 f i, j = f i-1, j-wi (wI0 then if j+now=n then inc(cj+now,aj); a:=c; end9; 20 3 3 解解 0-10-1 背

34、包问题的算法比较与分析背包问题的算法比较与分析 这四种算法都得到了验证，运行结果证明了算法设计是可行的，正确的。 通过对 O-1 背包问题的算法设计及时间复杂度分析可以看出。无论采用贪婪法 还是动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的 过程；但算法具体实现和数据结构的建立要用到递归和栈操作。比较贪婪法和 动态规划法。前者的时间复杂度低于后者，从耗费上而言优于后者。但后者的 实现算法可读性要优于前者。 动态规划算法的基本思想是把原问题分解为一系列子问题，然后从这些子 问题中求出原问题的解。回溯其实就是穷举，穷举所有的解，找出解中最优的 值。回溯法在包含问题的所有解的解空间

35、树中，按照深度优先的策略，从根结 点出发搜索解空间树。回溯法的基本思路是：确定解空间，建立解空间树，用 深度优先搜索算法递归搜索解空间树，并同时注意剪枝,常用的分枝一限界法有 最小耗费法，最大收益法。FIFO(先进先出)法等。0-1 背包问题的分枝一限界 算法可以使用最大收益算法。该算法跟回溯法类似。但分枝限界法需要 O() n 2 的解空间。故该算法不常用在背包问题求解。遗传算法是计算数学中用于解决 最优化的搜索算法，是一种进化算法。对于一个最优化问题，一定数量的候选 解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。通常解用 二进制 0 和 1 表示，进化从一个个体发生，然后一代

36、一代发生。在每一代中， 该种群的价值被评估，从当前种群中随机地选择多个个体（基于它们的适应度） ， 通过自然选择。 回溯法比分枝限界在占用内存方面具有优势。回溯法占用的内存是 0(解空 间的最大路径长度)，而分枝限界所占用的内存为 0(解空间大小)。对于一个子 21 集空间，回溯法需要 0(n)的内存空间，而分枝限界则需要 0(2n)的空间。虽然 最大收益或最小耗费分枝限界在直觉上要好于回溯法，并且在许多情况下可能 会比回溯法检查更少的结点，但在实际应用中，它可能会在回溯法超出允许的 时间限制之前就超出了内存的限制。 为了更直观更有效地分析动态规划法回溯法两种算法，下面分别对它们的 计算时间进

37、行测试。测试中,每个 0-1 背包问题的效益和重量分别为随机产生 的两组数据,其取值范围为0,999,背包容量定为 1125。为便于各算法间进行 比较，测试之前首先把物品按价值重量比的非增顺序排序。每次测试将程序运 行 100 次所得时间为运行 100 次的平均值。测试结果如下表所示18。 平均计算时间问题 规模动态规划法回溯法 50.0031120.003817 100.0093700.009630 150.0125500.013120 200.0151500.015780 250.0171800.018900 500.0264600.026710 1000.0418700.039840 2

38、000.0725500.058430 从表中的测试结果可以看出 当问题规模较小时，三种方法都有较好的稳 定性，计算时间都相差不多。随着问题规模的增大，各算法的计算时间都在增 大， 其中递归法的计算时间增长速度最快，当问题规模为 50，100 和 200 时， 其计算时间太长以致失去利用该法求解的意义，而动态规划法与回溯法则相对 稳定且计算时间也相差不多，但是当问题规模大到一定程度，回溯法要优于动 态规划法。 通过以上对 0-1 背包问题的求解分析，我们可以看到各种算法设计方法有 各内不同的特点，针对不同的问题领域，它们有不同的效率，对于求解 0-1 背 包问题，各算法的时问复杂度、优缺点以及改

39、进方法的比较如下表所示19: 动态规划 O(minnc,） n 2 可求得最优决 策序列 速度较慢 建立动态规划 递归方程 回溯法 O(n） n 2 能够获得最优 解 时间复杂度较 高 判断右子树时， 按效率密度 vi/wi 对剩余 对象排序 22 分枝-限界 法 O(） n 2 速度较快，易 求解 占用的内存较 大，效率不高 最大收益或最 小消耗分枝- 限界法，FIFO 法 遗传算法 O(n） n 2 能够解决传统 算法不能解决 的问题，能够 获得最优解 速度较慢，算 法不成熟 基于惩罚函数 修正方法和译 码方法 4 4 总结与展望总结与展望 本文就回溯法，分枝-限界法，遗传算法这 4 种求

40、解 0-1 背包问题的方法进 行研究比较，全方位的了解背包问题在实现的方法,以及各方法的优势和劣势， 通过比较，了解哪种方法是在什么样的情况下是最实用的方法，然后在以后的 实际运用中针对实际问题，找到最简单的方法解决 0-1 背包问题。 当然目前存在越来越多的算法来研究 0-1 背包问题，比如蚁群算法、微粒 群算法等群体智能算法在 0-1 背包问题求解方面具有的较好收敛速度、健壮性、 稳定性、算法简单等优点.最后,针对群体智能算法在求解 0-1 背包问题过程中 所出现的缺陷,提出了群体智能算法在 0-1 背包问题，还有一写混合的多有算法 来解决 0-1 背包问题等等 0-1 背包问题的求解方法

41、研究已经成为了当前众多科学关注的焦点，这不 仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中 广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问 题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了 计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于 NP 完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。 23 参考文献参考文献 1 王晓东.计算机算法研究与分析.电子工业出版社. 2 M.H.Alsuwaiyel 著，吴伟昶，方世昌等译.算法设计技巧与分析 . 电子工业出版社, 2004. 3 胡运权，运筹学教

42、程（第二版） ，清华大学出版社，2003 年. 4 曹新谱.算法设计与分析.湖南科技出版社，1984 年 11 月第 1 版 . 5 余祥宣. 崔国华. 邹海明. 计算机算法M.华中科技大学出版社， 2003. 6 李鸣山.郑海虹. 0-1 背包间题的多重分枝-限界算法 .武汉侧绘科 技大学学报，1995 . 20 (1). 7 霍红卫.许进.保铮.基于遗传算法的 0-1 背包问题求解.西安电子科 技大学学报， 1995.26（4）. 8 刘西奎.李艳.许进.背包问题的遗传算法求解研究阴.华中科技大学 学报(自然科学版)，2002，30(6)：89-90. 9 Mark Allen weiss

43、 著.冯舜玺译. 数据结构与算法分析C 语言描述 M.北京: 机械工业出版社， 2004. 1. 10 卢开澄.计算机算法引导-设计与分析(第 2 版)M=.北京:清华大学 出版社，2006. 11 郑宗汉.郑晓明. 算法设计与分析M.北京:清华大学出版社，2005. 12 陈莹.廖利.0-1 背包问题J.电脑知识与技术_研究开发， 2005.5:96-97. 24 13 朱红.算法设计与分析M.上海：上海科学技术文献出版社， 1989 14 张文修.梁怡.遗传算法的数学基础M.西安:西安交通犬学出版社， 2001. 15 COILEM TH，LEISERSON CE Introducetio

44、n to AlgorithmsM。 Massachusetts：The MIT Press，2002. 16 曾国清.0-l 背包问题的遗传算法求解J科技信息,2006(3):242 一 243 17 黄波.蔡之华. 0/1 背包问题及其解法研究 0/1 Knapsack Problem and Its Solution Methods Study 期刊电脑知识与技术(学术交流)COMPUTER KNOWLEDGE AND TECHNOLOGY ，2007 年 第 07 期. 18 雷鹏, 朱大铭, 马绍汉, 0/1 背包问题算法研究新趋势 2001 年全国 理论计算机科学学术会议 2001

45、年全国理论计算机科学学术会议论文集， 2001 年. 19 张景成,戴光明 基于 0/1 背包问题的算法探究 On the Algorithm of the 0/1 Knapsack Problem 期刊 电脑知识与技术（学术交流） COMPUTER KNOWLEDGE AND TECHNOLOGY， 2007 年 第 11 期. 25 致致 谢谢 弹指一挥间，四年的大学学习即将结束。在此，我要感谢华中师范大学汉 口分校信息科学与技术学院的各位领导和老师们，感谢关心帮助过我的同学们。 本文之得以完成，要特别感谢我的指导老师宾云峰、杨健老师。从论题的选择、 资料的收集、系统的研发到论文的写作，都是在宾云峰、杨健老师的悉心指导 和殷切关怀下完成的。他们严谨的治学精神、渊博的理论知识和丰富的实践经 验使我受益匪浅。在此，我向尊敬的宾云峰、杨健老师致以崇高的敬意和衷心 的感谢! 同时，向参加论文审阅和答辩的各位专家和老师表示衷心的感谢。