华中师范大学汉口分校毕业论文：0-1背包问题的算法研究与实现

华中师范大学汉口分校毕业论文：0-1背包问题的算法研究与实现

会员共享“背包问题本科毕业论文的算法研究和实施”，可以在线阅读。有关背包问题本科毕业论文的更多相关“算法研究和实施”（28页的收藏版）”，请在Sany办公室搜索。

1. Algorithm Research and Implementation of Backpacking Problems of Undergraduate Graduation Thesis of Hankou Branch of Central China Normal University 0-1 Department of Department of Science and Technology: School of Information Science and Technology Major: Computer Science and Technology Grade: 2005 Student: Liu Nianxue No.: 2005911032 Instructor: Bin Yunfeng, Yang Jian Original Statement of thesis of Hankou Branch of Central China Normal University I solemnly declare that the paper提交的是我在主管的指导下独立取得的研究结果。除了本文中专门标记和引用的内容外，本文不包含其发表或撰写的任何其他个人或集体作品。我完全意识到，这一说法的法律后果是由我承担的。论文签名的作者：日期：年，月，日期，版权，论文的作者，对学校保证和使用论文的法规的完全理解，并同意学校保留它

2。将论文的副本和电子版本提交相关论文管理部门或机构，从而可以审查和借用该论文。我授权省级杰出学士学位论文选择机构将本论文的全部或部分内容编译到相关的数据库中进行搜索。我可以通过复制，减少打印或扫描来保存和编译本文。该论文属于1。机密性，该授权信在_年前解密后适用。 2。不机密。 （请在上面的相应框中输入“”论文作者的签名：日期：年，月，日，教练签名：日期：年，月，日，日，目录摘要1关键字1abtract2key Words2Key Words21介绍31.1提案和研究显着性31.2算法研究的分析算法问题31.3.3 31.3 Backake of Backpack问题31.3 Backake Backeck of Backeck of Backake of Backeck of Backeck of Backeck of Backeck 3 31. 42 0-1 abt 42 0-1 2. 42 0-1 2. 42 0-1 52.1 0-1背包问题31.2背包问题算法研究的分析31.3主题的主要研究内容42 0-1背包问题的实施52.1 0-1背包问题52.1 0-1背包问题31.3主要研究内容31.3背包问题42 0-1背包问题的实施52.1 Backpack问题52.1 BackApt 42.1 BackApt 42 BackApt 42 BackApt 42 BackApt 42 BackApt 42 BackApt 42 BackApt 42 BackApt 42 Backage of 42 BackApt 42 BackApt 42。背包问题52.1 0-1背包问题52.2 0-1背包问题

3。动态编程中的问题的实施52.2 0-1回溯方法中背包问题的实现82.3 0-1在分支限制方法中实施背包问题122.4 0-1遗传算法中背包问题的实现163算法和分析解决方案和分析的算法和分析0-1背包问题204典型问题22.典型的问题22. Cravess 22 Cravess 2 25 Contract 2 23在操作研究领域常见，也是算法设计分析中的经典问题。在理论和实践中，对该问题解决方案方法的研究都具有重要意义。已经研究了许多经典方法来解决此问题，并进行了此问题的探索和应用。在高级理论的指导下，解决0-1背包问题具有重要的特征，例如科学，高效，经济，灵活和方便。然后，为了解决背包问题，第一个先决条件是设计好算法

4。如果您想找到背包问题的解决方案，则必须首先设计算法。本文使用动态编程方法，回溯方法，分支限制方法和遗传算法来对背包问题，0-1背包问题和简单的0-1背包问题进行算法设计和时间复杂性分析，并提供特定的算法设计和实施过程。并使用特定的示例来描述以不同方法解决问题时的算法的基本思想，然后详细比较这四种算法以解决0-1背包问题，总结了实施四种方法的优点和缺点，并得出结论。如何将背包问题应用于实际问题，设计算法适合以目标方式解决实际的0-1背包问题，并且可以很好地解决实际问题，这是计算机工人不断思考和研究的领域。关键字：0-1背包动态编程回溯方法分支限制方法遗传算法摘要：Knapsack Prob

5。LEM是一个典型的NP-C问题，也是对公共操作研究领域的经典问题的算法设计和分析。在理论上还是实践中，研究问题的解决方案非常重要。经过一些研究，许多解决此问题的经典方法

6。EM已经提出了，对这个问题和应用研究的探索一直在进行。在高级理论的指导下，有独特的特征，例如科学，高效，经济，灵活和方便的特征，以解决0-1背包问题。

7。psack问题，第一个前提是设计一个良好的算法。要寻求背包问题的解决方案，首先必须使用动态编程来设计算法。在本文中，四种方法，例如动态编程，回溯，分支 - 绑定方法和遗传算法尊重

8。旨在针对背包问题，0-1背包问题和简单的0-1背包问题进行算法设计和分析时间复杂性，并给出了该过程的特定算法设计和实现。描述详细介绍了使用特定考试的基本概念

9.在以不同方式解决问题的过程中，然后旨在解决0-1背包问题，详细比较四种算法并总结四种方法实现的优点和缺点，并得出结论。

10。IGN针对解决0-1背包问题的实用算法并很好地解决了实际问题，这是计算机工人不断思考和学习的领域。关键词：0-1背包问题动态编程回溯分支 - 界方法遗传算法1简介1.1提案和研究意图

11。0-1背包问题是计算机科学中非常经典的优化问题。这也是NP难度的事实证明的问题。它是由默克尔（Merkel）和海尔曼（Hellman）于1978年提出的。它的主要思想是假设某人的重量不同。此人通过秘密选择部分物品并将其放置在背包中来加密消息。背包中物品的重量是公开的，并且要选择的所有可能的项目都是公开的，但是背包中的项目是机密的。在某些限制中加重体重和列出可能的项目是计算上不可用的。背包问题是一个众所周知的无法估量的问题。背包系统被快速加密和解密，并引人注目。但是，大多数一次性背包系统都被解密了，因此现在很少有人使用它。这个问题有许多解决方案，例如贪婪算法，动态编程，分支边界，回溯方法和旧版

12。传输算法等。其中，回溯是一种常见的解决方案方法。多年来，背包问题吸引了许多理论和实践工人，以对此问题进行深入研究。从理论上讲，尽管背包问题具有简单的结构，但它具有组合爆炸的性质。在实际应用中，可以通过背包问题描述和解决许多工业问题，例如基金计算，货物持有加载，存储分配等是典型的申请示例。如何将背包问题应用于实际问题并充分解决实际问题是计算机工人不断思考和研究的领域。 1.2对0-1背包问题算法研究的分析0-1关于背包问题的算法研究主要是通过算法设计和分析知识，设计和编程算法来设计和实施的，这些算法，设计和编程算法可以尽可能有效地解决相关问题，并能够通过算法的基础技术来进一步分析算法的复杂性，从 分析

13。提高算法设计和分析的应用功能的方法。 0-1backpack是一个非常典型的优化问题，研究它具有重要的实际意义。这不仅是因为它在结构上很简单，还可以为将更复杂的问题作为子问题奠定一个理论基础，并且具有很高的理论研究价值，而且还因为它是对许多实用工程应用问题的一般描述，它在许多实际的实际问题中具有非常广泛的应用背景，例如项目决策等许多实际问题。它包含背包问题中设计状态和方程式的最基本思想，并且在经济管理，资源分配，投资决策，加载设计和其他领域中具有重要的应用价值。在计算理论中，它是NP-C的一个完整问题，其计算复杂性传统上是通过动态编程来解决的。背包旅行的问题在于，在资源有限的条件下，

14。有效分配资源的问题，该资源追求最大的总利润。 1.3主题的主要研究内容1.3.1背包问题背包问题的描述是整数规划中的一种特殊类型，并且在现实生活中广泛使用。如果可以提出有效解决此问题的有效算法，则具有良好的经济价值和决策价值。问题的一般描述是：旅行者是背包和攀爬，背包的最大负载轴承为m，并且可以选择加载n个项目。第i-the项目是Wi，值为Pi。假设项目I（0xi1）的一部分放置在背包中，则值为XIPI。由于背包的最大负载轴承为m，因此要加载的项目的总质量不超过M。问旅行者如何选择将项目加载到背包中的项目，以便要加载的项目值的总和达到最大值。背包问题的数学描述如下：需要找到N元素向量（X1，X2XN），并且在约束的情况下：

15。使目标函数，其中1英寸； M0; Wi0; PI0。任何满足约束的向量都是可行的解决方案，可行的解决方案使目标函数达到最大值是最佳解决方案1。1.3.20-1背包问题0-1背包问题0-1背包问题提出了给定的N类型的项目和1个背包。项目i的重量是Wi，其值是PI，背包的容量是M。应该如何加载到背包中的项目，以使背包中项目的总价值是最大的？当选择物品包装人的背包时，每个项目I只有两个选项，即，将它们放在背包中，而不将其加载到背包中。项目我不能多次放入背包，也不能仅将其加载到项目i的一部分中。此问题称为0-1背包问题。问题的符号表示象征0-1背包问题是，给定M0，Wi 0，pi 0，1in，需要找到N-元素0-1 0-1矢量向量（x）

16. 1, x2xn), X i = 0 or 1, 1in, so that, and reaches a maximum of 2.2 0-1 Implementation of backpack problems 2.1 0-1 Implementation of backpack problems in dynamic planning 2.1.1 The basic principle of dynamic programming and analysis of dynamic planning algorithm is to decompose the problem to be solved into several sub-problems, first solve the sub-problems, and then obtain the solution of the original problem from这些子问题的解决方案。但是，分解的子问题通常并非彼此独立。不同子问题的数量通常仅是多项式的顺序。如果您可以保存解决已解决的子问题的答案，并在需要时找到获得的答案，则可以避免大量重复计算，从而获得多项式时间算法。它将已知问题划分为许多子问题，按顺序解决子问题，在每种情况下，都列出了各种情况的本地解决方案，并选择最有可能根据条件从中产生最佳结果的人。

17。其余。先前的子问题为后续子问题提供了信息，并减少了计算量，最后一个子问题的解决方案是问题解决方案。使用此方法解决0-1背包问题的主要步骤如下：分析最佳解决方案的结构：最大的子结构属性；建立递归方程；计算最佳值；并构建最佳解决方案4。动态编程算法中决策的每个步骤都基于上一步的状态参数确定此步骤的状态参数的设置。也就是说，从初始状态到最终状态，它必须经过多个过程，经过不同的状态，并根据先前的状态不断决定下一个状态，从而形成决策顺序，最后解决整个问题。这是典型的多段决策的特征。从上面的动态编程方法介绍，可以看出，0-1背包问题与多阶段决策的特征一致，并且具有重叠的子问题。因此，在设计0-1背包问题解决方案时，可以将整个项目放在背包上。

18。这被认为是拾取物品的过程。 2.2.2实现0-1背包问题最佳子结构属性0-1背包问题具有最佳的子结构属性。假设（Y1，Y2YN）是针对给定0-1背包问题的最佳解决方案，然后（Y2，Y3YN）是对以下相应的子问题的最佳解决方案：如果否则，让（Z2，Z3ZN）成为上述问题的最佳解决方案，并且（Y2，Y3YN）不是最佳的解决方案，并且可以从中可以看出。因此，C这表明（Y1，Z2ZN）是针对给定0-1背包问题的更好解决方案，因此（Y1，Y2YN）不是给定0-1背包问题的最佳解决方案。这是一个矛盾的1。递归关系允许0-1背包问题的子问题的最佳值为m（i，j），即，当背包容量为j时，m（i，j）是0-1背包问题的最佳值，并且可以选择项目是i，i+1，i+1，n。由0-

19. 1个背包问题的最佳子结构属性，以及用于计算M（i，j）的递归公式，如下所示：算法描述基于上述讨论。当Wi（1in）是一个正整数时，使用M（i，j）的相应值来存储2D阵列m。可以将解决0-1背包问题的动态编程算法背包设计为输入：TemplateVoid Knapsack（类型V，Int W，Int C，Int N，Type * * M）int Jmax = min（WN-1，C）; for（int j = 0; j = jmax; j+）mnj = 0; for（int j = wn; j1; i-）jmax = min（wi-1，c）; for（int j = 0; j = jmax; j+）mij = mi+1j; for（int j = w

20。i; j = w1）m1c = max（m1c，m2c-w1+v1）; TemplateVoid trackback（type * * m，int w，int c，int c，int n，int x）for（int i = 1; i = n; i+i+）if（mic = mi = mi+1c）xi = 0; else xi = 1; c- = wi; xn =（MNC）？1：0; 1计算复杂性分析求解0-1背包问题的复杂性是0（Minnc，2n。动态编程主要是为了求解最佳决策序列。当最佳决策序列包含最佳决策序列时，最佳决策分区，即动态编程方程，可以帮助解决问题，可以解决问题2.在2.中有效地提出了有效的2.。回溯方法2.2.1基本原理和回溯方法的分析

21。这是一种系统地搜索问题答案的方法。为了实现回溯，首先有必要为问题定义解决方案空间，该空间必须至少包含一个解决问题的解决方案（可能是最佳）。回溯方法需要为问题定义一个解决方案空间，该空间必须至少包含一个解决问题的解决方案（可能是最佳）。使用递归回溯方法来解决背包问题的优点是，其算法很简单，并且可以完全遍历搜索空间，并且绝对可以找到解决问题的最佳解决方案。但是，由于该问题的解决方案的总数总数，随着对象n的数量增加，其溶液的空间将在n个级别上生长。当n在一定程度上很大时，使用此算法来解决背包问题将是不现实的。下一步是组织解决方案空间，以便可以轻松搜索。典型的组织方法是图形或树。一旦定义了对组织方法的理解，该空间就可以根据深度优先的方法从起始节点进行搜索，并使用边界函数

22.数字避免移动到不可能解决方案的子空间。 2.2.2 0-1，用于实现背包问题的回溯方法的算法描述。回溯方法是一种系统地搜索问题答案的方法。为了实现回溯，首先有必要为问题定义解决方案空间，该空间必须至少包含一个解决问题的解决方案（可能是最佳）。一旦空间定义的组织者选择一个子集并打包它们以获取最大的利润，则应将解决方案空间组织到子集树的形状中。首先，形成了递归算法，以找到可用的最大利润。然后，将算法改进以形成代码。改进的代码在获得最大利润时会发现背包中包含的对象集合。左子树代表一个可行的节点，该节点在任何时候都会移动到它，当右子树可能包含一个比当前最佳解决方案更好的解决方案时，请移动到它。决定是否移至右子树的一种简单方法

23。方法是r是尚未遍历的对象的好处的总和，并将R添加到CP（当前节点获得的好处）。如果（R+CP）BESTP（当前最佳解决方案的好处），则无需搜索正确的子树。一种更有效的方法是按收入密度VI/WI对剩余的对象进行排序，以减小密度的顺序填充背包的剩余容量，并在遇到无法放置在背包中的第一个对象时使用部分。用于解决0-1背包问题的回溯算法如下：Templateclass Knap Friend Typep knapsack（typep*，typew*，typew，typew，int）;私人：typep bund（int i）; void backtrack（int i）;打字C; /背包容量

24. int n; /打字的项目数*w; /项目重量阵列Typep*p; /项目值阵列打字CW; /当前重量Typep CP; /当前值typep bestp; /当前最佳值； templateVoid Knap：Backtrack（int I）如果（in）/到达叶节点bexp = cp; return; if（cw+wibestp）/输入正确的子数字回溯（i+1）; templateTepypep; /剩余容量打字b = cp; /加载项目以减小单位重量值的顺序（i = n＆wi = c

25。左）cleft- = wi; b+= pi; i+; /如果（i = n）b+= pi*cleft/wi; return b;类对象朋友int knapsack（int*，int*，int*，int，int）; public; int oterator = ad）;私人：int id; float d; ; templateTypep knapsack（typep p，typep w，typew c，int n） /initialize typew w = 0; typep p = 0;对象*q = new Objectn; for（int

26。i = 1; i = n; i+）qi-1.id = i; qi-1.d = 1.0*pi/wi; p+= pi; W+= Wi;如果（w = c）返回p;/按单位权重值（q，n）加载所有项目/排序； knapk; kp = new typepn+1; kW = new typewn+1; for（int i = 1; i = n; i+）k.pi = pqi-1.id; k.wi = wqi-1.id; k.cp = 0; k.cw = 0; kc = c; kn = n; K.Bestp = 0; /返回搜索K.BackTrack（1）; deleteq; Deletek.w; DELETEK.P;恢复k，

27。最好的; 1算法效率，因为O（n）需要时间来计算上限函数，在最坏的情况下，有需要上限函数的O（）右子节点，因此计算计算0-1背包问题的回溯算法所需的计算时间复杂性是O（N）。回溯方法的改进主要是确定是否移至右子树。一种更有效的方法是根据福利密度VI/WI对剩余的对象进行排序，以减小密度的顺序填充背包的剩余能力，并在遇到无法放置在背包中的第一个对象时使用部分。回溯算法的运行时间取决于其在搜索过程中生成的节点的数量。边界功能可以大大减少生成的节点数量，从而节省大量不必要的搜索，从而更快地进行搜索。拨打边界功能需要花费时间来计算上边界。在最坏的情况下，有o（）节点需要调用边界功能，这会花费O（n

28.）时间，因此该算法的时间复杂性为O（n）12。回溯方法的另一个重要特征是在搜索执行时生成解决方案空间。在搜索期间的任何时刻，仅保留从启动节点到当前可扩展节点的路径。空间要求是O（启动节点的最长路径的长度）。因此，此处的算法的空间复杂性是O（n）。回溯方法是算法设计的基本方法之一。它适合解决一些问题，涉及找到一组解决方案或找到满足某些限制的最佳解决方案。它也适用于解决大量组合的问题。 2.3 0-1在分支限制方法中的背包问题实施2.3.1基本原理和分支限制方法的分析。分支和边界是系统地搜索解决方案空间的另一种方法。它与回溯方法之间的主要区别在于电子节点的扩展方法（扩展节点）。每一个生活

29。如果有节点，只有一次，它们将成为电子节点。当节点成为电子节点时，可以通过从节点一个移动来达到所有新节点。在生成的节点中，放弃那些无法得出的节点（最佳）可行解决方案，添加剩余节点表，然后从表中选择一个节点作为下一个E节点。选定的节点是从旋转节点表中获取的，并扩展，并且在解决方案或活动表被发现为空之前，扩展不会结束。有两种常用的方法可以选择下一个电子节点：第一int-In-int-int Out（FIFO），即从节点表中取出节点的顺序与添加节点的顺序相同，因此节点表的性质与队列相同。在此模式下，每个节点都具有相应的消耗或益处。如果您寻找最少消耗的解决方案，则可以在最小堆中建立肿胀的节点表，而下一个电子节点是最小的消耗量

30。FIFO分支定界符。如果您想搜索具有最大好处的解决方案，则可以使用最大堆构建惰轮。下一个电子节点是带有最大好处的惰轮。 2.3.2 0-1背包旅行问题的实现。解决方案空间树上的FIFO分支定界符方法与从根节点开始的宽度优先搜索非常相似。他们的主要区别是，在FIFO分支划界中不可行的节点将无法搜索。背包问题的最大福利分支分界算法可以使用划界功能来计算其余节点的上返回限制，以便扎根于剩下的节点的子树中任何节点的返回值不能超过Upprofit。其余节点的最大堆将Upprofit用作钥匙值范围。在子集树中执行最大收益分支分隔搜索的功能首先初始化可移动节点的最大堆，并使用数组BESTX记录最佳解决方案。

31。由于需要连续使用收入密度来排序，因此该项目的索引值将相应地更改，因此函数产生的结果必须映射回初始项目索引。函数中的循环首先测试电子节点左子女的可行性。如果可行，则将其添加到子集树和秋千节点的队列（即最大堆）。仅当节点的右子树的划界值表明可以找到最佳解决方案时，只有将右子添加到子集树中并排队。然后，主要算法被描述为：类对象朋友int knapsack（int *，int *，int，int，int *）;公共：int operator = ad）;私人：int id; float d;/单位重量值；模板类旋转；班级

32。bbnode的朋友诺普；朋友int knapsack（int *，int *，int，int，int *）;私人：bbnode *parent; /指向父节点bool lchild的指针； /左儿子节旗；模板类HeapNode朋友符号；公共：操作员typep（）const返回Uprofit；私人：Typep Uprofit， /名称值上限利润； /名称值对应于节点打字重量； /名称重量对应于节点int级别； /生活结

33。点在子集中BBNODE *ptr中的点的层号; /指向子集树中的相应节点； templateclass knap friend typep knapsack（typep *，typew *，typew，int，int *）;公共：Typep MaxKnapsack（）;私人：maxheapheapnode*h; Typep绑定（int i）; void addlivenode（typep up，typep cp，typep cw，bool ch，int级别）; bbnode *e; /指向扩展节点打字C的指针; /背包容量I

34。ntn; /打字的项目总数 *w; /项目重量阵列Typep *p; /项目值阵列打字CW; /当前包装重量Typep CP; /当前软件包值int * bestx; /最佳解决方案； TemplateTypep knap：MaxKnapsack（）/优先级队列分支边界方法，返回最大值，BESTX返回最佳解决方案/将最大堆容量定义为1000 H = new Maxheapheapnode（1000）; /分配BESTX BESTX的存储空间= new Intn+1; /初始化int i = 1; E = 0; CW = CP = 0; typep bestp = 0; /当前最佳值打字

35。UP=绑定（1）; /值上限/搜索子集空间树，而（i！= n +1）/非叶节点/检查当前扩展节点的左子节点typew wt = cw +wi; if（wtbestp）bestp = cp+pi; AddLivenode（向上，CP+PI，CW+WI，TURE，I+1）;向上=绑定（i+1）; /检查当前扩展节点的正确儿子节点，如果（up = bestp）/右子树可能包含最佳解决方案addlivenode（up，cp，cw，cw，false，i+1）; /检索下一个扩展节点hapnoden; h-deletemax（n）; e = n.ptr; cw = n.Waight; cp = n.prof

36。 up = n.uprofit; i = n.Level; /构造（int j = n; j0; j-）bestxj = e-lchild的当前最佳解决方案; e = e-parent;返回CP; 12.4 0-1在遗传算法中实施背包问题2.4.1基本原理和遗传算法遗传算法作为解决复杂问题的有效方法，密歇根大学的霍尔·兰德（Hol-land of Michigan）和他的同事在1975年首次提出了基于自然选择和进化机制的美国同事。这是一种基于自然选择的概念，最优胜品的生存和物种遗传学的生存的概念。它将问题的每个可能解决方案视为人群中的个体（染色体），将每个染色体编码为字符串，然后对每个染色体使用预定的目标函数

37。每个人评估并给出适应值。该算法将基于自适应值执行优化过程。遗传算法的优化过程是通过选择，杂交和突变等遗传算子特异性实现的。它的搜索能力由选择操作员和杂交操作员确定。突变操作员确保算法可以搜索问题空间中的每个点，以便它具有搜索全球最佳功能的能力。遗传算法的效率和强度可以通过荷兰的模式定理和隐式并行性来解释。在遗传算法中，定义长度较短，较低顺序和适应值的模式的期望值超过了人口中平均自适应值的呈指数增加，并且该结论成为遗传算法的基本定理。遗传算法可以被视为定义域l维定义域的矢量null问题B。有一个适应性函数，其中适应性函数被随机选择，交叉和突变的操作以找到该功能的最大值，即，遗传算法被认为是

38。搜索技术在特定空间中的最大值。在运行中，新点主要由交叉操作产生。传统的跨界运营商是随机操作。后代只是继承了“父母”基因的一部分，不能保证后代的表现比父母的表现更好。此外，以这种方式的点对点搜索范围是有限的，它可能会忽略附近的更好的点，而导致结果收敛到本地最优性。 2.4.2 0-1背包问题的实现（1）编码方案：使用遗传算法解决0-1背包问题。 A very natural coding scheme is to use the amount X to be solved to represent the binary string Xi,j=1,2,n,xi=1 that grows into n. Put the object j in the backpack, and xj means that the object j is placed in the backpack. (2) Design of fitness function: Based on the above encoding, the fitness function of backpack problem is constructed according to the proposed method of handling constraints of penalty function: (X): (X)=-here

39. For all feasible solutions X that satisfy bar C, the penalty function Va(X)=0 The penalty function can be used with logarithmic functions, linear functions, quadratic functions, etc., respectively, and is sequentially used as the degree of invasion increases. (3) Selection operation: Select chromosomes according to the selection probability, and use the above-mentioned individuals as the 0th generation. For each chromosome, calculate the cumulative probability Qi, generate a random number r from the interval (0, Qi). If Qi -1rQi, select the i-th chromosome, repeat the above operation to copy the chromosome. (4) Crossing operation: determine whether a chromosome is a living chromosome. If it is a living chromosome, the chromosomes will be crossed, and a single-point crossing method is generally adopted. (5) Mutation operation: Chromosomal mutation adopts site mutation. Make the flexibility after the mutation at least greater than or equal to the original fitness, otherwise reselect the mutant position for mutation. Repeat this several times, if the fitness value is not increased

40. The mutation fails. (6) When the result obtained by a certain generation meets the requirements or the current algebra is equal to the end of the algebra, the algorithm ends to obtain the result. Otherwise, repeat the above steps (3) and (4) 7. Then the main algorithm is described as: procedure search(k,v:integer); Search for the kth item, the remaining space is v var i,j:integer; begin if v=best then exit; sn is the weight of the first n items and if kwk then search(k+1,v-wk); search(k+1,v);结尾;结尾; l DP Fi,j is the signs selected from the first i items to put the volume exactly j, which is Boolean. Implementation: A: Convert the optimization problem into a decisive problem fi, j = f i-1, j-wi (wI=j0 then if j+now=n then inc(cj+now,