《回溯法和分支限界法解决0-1背包题》由会员分享，可在线阅读，更多相关《回溯法和分支限界法解决0-1背包题（14页珍藏版）》请在金锄头文库上搜索。
1、真诚为您提供优质参考资料，若有不当之处，请指正。0-1背包问题计科1班 朱润华 2012040732方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有0-1赋值。例如n=3时，解空间为： （0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1） 然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C
2、。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c 0, wi 0, vi 0 , 1in.要求找一n元向量(x1,x2,xn,), xi0,1, ? wi xic,且 vi xi达最大.即一个特殊的整数规划问题。二、回溯法步骤思想描述：0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r=bestp时，可剪去右子树。计算右子树上
3、界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。例如：对于0-1背包问题的一个实例，n=4,c=7,p=9,10,7,4,w=3,5,2,1。这4个物品的单位重量价值分别为3,2,3,5,4。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为1,0.2,1,1，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间
4、树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。三、回溯法实现代码：#include stdafx.h #include using namespace std; template class Knap template friend Typep Knapsack(Typep ,Typew ,Typew,int); private: Typep Bound(int i); void Backtrack(int i); Typew c; /背包容
5、量 int n; /物品数 Typew *w; /物品重量数组 Typep *p; /物品价值数组 Typew cw; /当前重量 Typep cp; /当前价值 Typep bestp;/当前最后价值 ; template Typep Knapsack(Typep p,Typew w,Typew c,int n); template inline void Swap(Type &a,Type &b); template void BubbleSort(Type a,int n); int main() int n = 4;/物品数 int c = 7;/背包容量 int p = 0,9,10
6、,7,4;/物品价值 下标从1开始 int w = 0,3,5,2,1;/物品重量 下标从1开始 cout背包容量为：cendl; cout物品重量和价值分别为：endl; for(int i=1; i=n; i+) cout(wi,pi) ; coutendl; cout背包能装下的最大价值为：Knapsack(p,w,c,n)endl; return 0; template void Knap:Backtrack(int i) if(in)/到达叶子节点 bestp = cp; return; if(cw + wi bestp)/进入右子树 Backtrack(i+1); template
7、 Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) b += pi/wi * cleft; return b; class Object template friend Typep Knapsack(Typep,Typew ,Typew,int); public: int operator =a.d); private:
8、int ID; float d; ; template Typep Knapsack(Typep p,Typew w,Typew c,int n) /为Knap:Backtrack初始化 Typew W = 0; Typep P = 0; Object *Q = new Objectn; for(int i=1; i=n; i+) Qi-1.ID = i; Qi-1.d = 1.0 * pi/wi; P += pi; W += wi; if(W = c)/装入所有物品 return P; /依物品单位重量价值排序 BubbleSort(Q,n); Knap K; K.p = new Typep
9、n+1; K.w = 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; K.c = c; K.n = n; K.bestp = 0; /回溯搜索 K.Backtrack(1); delete Q; delete K.w; delete K.p; return K.bestp; template void BubbleSort(Type a,int n) /记录一次遍历中是否有元素的交换 bool exchange; for(int i=0; in-1;i+) exchange = false ; for(int j=i+1; j=n-1; j+) if(aj=aj-1) Swap(aj,aj-1); exchange = true; /如果这次遍历没有元素的交换,那么排序结束 if(false = exchange) break ; template inline void Swap(Type &a,Type &b) Type temp = a; a = b; b = temp; 四、程序运行结果：五、回溯法解决0-1背包问题复杂度分析：计算上界需要O(
