《01背包问题的多种解法》由会员分享，可在线阅读，更多相关《01背包问题的多种解法（11页珍藏版）》请在金锄头文库上搜索。
1、一、问题描述0/1背包问题：现有n种物品，对1=iC(n1,W),说明第n个物品被装入了背包中，前n-1个物品被装入容量为WWn的背包中；否则，第n个物品没有装入背包中，前n-1个物品被装入容量为W的背包中。依此类推，直到确定第一个物品是否被装入背包为止。由此，我们可以得到如下的函数:0c(i,j)C(i1,j)1,jjwC(i,j)C(i1,j)根据动态规划函数，用一个(n1)(W1)的二维数组C存放中间变量，Cij表示把前i个物品装入容量为j的背包中获得的最大价值。设物品的重量存放在数组wn中，价值存放在数组vn中，背包的容量为W,数组Cn1W1存放迭代的结果，数组xn存放装入背包的物品，
2、动态规划解0-1背包问题的源代码在文件夹动态规划法中。回溯法分析：用回溯法解0_1背包问题时，会用到状态空间树。在搜索状态空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索，否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+rwbestp时，可剪去右子树。计算右子树中解的上界可以用的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界，用此值来剪枝。为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要
3、顺序考察各物品即可。在实现时，由MaxBoundary函数计算当前结点处的上界。它是类Knap的私有成员。Knap的其他成员记录了解空间树种的节点信息，以减少函数参数的传递以及递归调用时所需要的栈空间。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数MaxBoundary,以判断是否可以将右子树减去。进入左子树时不需要计算上界，因为其上界与父结点的上界相同。在调用函数Knapsack之前，需要先将各物品依其单位重量价值从达到小排序。为此目的，我们定义了类Objiect。其中，运算符与通常的定义相反，其目的是为了方便调用已有的排序算法。在通常情况下，排序算法将待排序元素从小到大排序。
4、在搜索状态空间机寸，由函数Backtrack控制。在函数中是利用递归调用的方法实现了空间树的搜索。具体的代码见回溯法文件夹。限界分支法：在解0-1背包问题的优先队列式界限分支法中，活结点优先队列中结点元素N的优先级由该结点的上界函数MaxBoundary计算出的值uprofit给出。该上界函数在0-1背包问题的回溯法总已经说明过了。子集树中以结点N为根的子树中任一个结点的价值不超过N.profit。因此我们用一个最大堆来实现活结点优先队列。堆中元素类型为HeapNode,其私有成员有uprofit,profit,weight,level,和ptr。对于任意一个活结点N,N.weight是活结点
5、N所相应的重量；N.profit是N所相应的价值；N.uprofit是结点N的价值上界，最大堆以这个值作为优先级。子集空间树中结点类型为bbnode。在分支限界法中用到的类Knap与0-1背包问题的回溯法中用到的类Knap很相似。他们的区别是新的类中没有了成员变量bestp,而增加了新的成员bestx。Bestxi=1,当且仅当最优解含有物品io在类Knap中有四个函数：(1)上界函数MaxBoundary。,计算节点所对应价值的上界；(2)函数AddLiveNode()是将一个新的活结点插入到子集树和优先队列中；(3) 函数MaxKnapsack()实施对子集树的优先队列式分支界限搜索。其中
6、假定物品依其单位价值从大到小已经排好序。相应的排序过程会在算法的预处理部分完成。算法中E是当前扩展结点；cw是该结点的重量；cp是该结点的价值；up是价值上界。算法的while循环不断扩展结点，直到子集树的一个叶结点成为扩展结点为止。此时优先队列中所有活结点的价值上界均不超过该叶结点的价值。因此该叶结点相应的解为问题的最优解。在while循环内部，算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。(4) 函数Knapsack(浣成对输入数据的处理。其主
