基于C#的0―1背包问题的回溯算法.docVIP

基于C#的0―1背包问题的回溯算法 　　摘要：0-1背包问题是经典的NP问题。该文对0-1背包问题的回溯算法进行了分析，用C#实现该算法。 　　关键词：0-1背包；回溯 　　中图分?号：TP311 文献标识码：A 文章编号：1009-3044（2016）36-0076-02 　　The B_tracking Algorithm of 0-1 Knapsack Problem Based on C# 　　CHEN Zi-li 　　（Fujian Chuanzheng Communications College， Fuzhou 350007， China） 　　Abstract： The 0-1knapsack problem is a classic NP problem. In this paper， the 0-1 knapsack problem and its algorithm is analyzed， the algorithms is based on B_tracking algorithm. And carry out the algorithms in the C#. 　　Key words： 0-1 Knapsack； b_tracking algorithm 　　1 0-1背包思想 　　0-1背包问题的思想：如果n个物品的重量和价值分别为[wi0]和[pi0]，背包的大小设置成[ci0]，应该怎样往背包中放置物品可以达到最大值或者最佳装载方式？[5] 　　在实际进行装包操作时，规定每种物品只能载入一次，而且每种物品只能执行载入或者不载入操作，则把该问题叫做0-1背包问题。 　　给定[wi]0，c0，[vi]0，[1≤i≤n]，寻求一个n元0-1向量[（x1，x2，...，xn），xi∈{0，1}，][1≤i≤n]，使得[i=1nwixi≤c]，而且[i=1nvixi]是最值。 　　[maxi=1nvixi] [i=1nwixi≤cxi∈{0.1}，1≤i≤n] 　　2 几种解法的比较 　　2.1 回溯法 　　回溯法就是为问题声明一个解集合，这个集合存在一个可能是最优的解。递归回溯法算法思想非常简单，能够对有哪些信誉好的足球投注网站空间进行遍历，必然可以找到背包问题的最优解，缺点是背包问题解集合将随着物品数量n的变大以2的几何级数增长，当n大到一定程度上，要遍历有哪些信誉好的足球投注网站空间需耗费大量的时间和资源，因此当物件数过多的时候，就很难依靠回溯法来求解。 　　2.2 动态规划算法 　　动态规划指的是把复杂的多阶段问题分解成相对简单的单阶段问题。对于背包问题可以用穷举法对子过程进行求解，并且决策的有哪些信誉好的足球投注网站范围会因为条件的增多而变小，这样求解也更简单。 　　2.3 贪心算法 　　贪心方法的使用可以降低求解时计算的复杂度。贪心算法不是片面追求最优解，因此不理会所有情况，所以不象回溯法那样进行遍历，一般情况下，就以目前情形最为最优的 。 　　2.4 分枝限界法 　　分枝界限与回溯法拓展E节点的方法不一样，为另一种全面地遍历解集合的方法，按这种算法，任何活节点只可能一次改变为E节点。当某节点一旦改变成E节点，会同时产生一些新节点（也就是分枝），新产生的节点是从原节点跳转一步实现的。产生的新节点里，只留下有希望得到行得通解的节点，添加到活节点表，剩下的抛弃。接着从活节点表里挑选节点再进行拓展，最后就可以得到最后解，并且活动表清空了。 　　3 回溯算法 　　回溯法为一种在问题的结果空间树T上查询问题答案的算法。回溯法在全部解的结果空间树中，依照深度优先的方法，从根节点开始查询结果空间树。算法有哪些信誉好的足球投注网站至结果空间树的每个节点时，先看看是不是不存在结果。假设确定不存在，那么忽略该子树，继续向其父节点进行回溯，反之，使用该子树，仍然以深度优先的方法进行查询。当回溯法来寻找结果时，一定要回溯到顶点，并且，顶点节点的全部子树都查找完才停止。这样，按照深度优先的策略全面查询问题的结果的算法叫做回溯法，可以解决组合数很多的情况。 　　假设选取回溯法来解决0-1背包问题，可以用在采取子集数表示0-1背包问题的结果集合。执行查找结果空间树时，如果左节点是能用的节点，查找行为转到它的左子树。那什么时候进入右边的子树查找呢？那就是只有在右边子树里有希望找找最优解的时候，才转到右边子树查询。要不然就把右子树删除。此过程由上界函数来完成。假定r是现在还没有使用的剩下物品总价值，cp是现在已有的价值，yestp为目前最优的价值。那么在cp+r=yestp时，允许删除右边子树。寻找右边子树里上届解的一种更先进的方法是把剩下物品按照它的价值/单位重量进行排定顺序，顺序载入物品，直到载不进去时，再载入这物品的局部实现载满背包。这样，价值等于右边子树