蛮力法动态规划法回溯法和分支限界法求解01背包问题

1、、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/1 背包问题。注：0/1背包问题：给定n种物品和一个容量为C的背包，物品i的重量 是Wi，其价值为Vi，背包问题是如何使选择装入背包内的物品，使得装入背 包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包 两种选择。、所用算法的基本思想及复杂度分析：1. 蛮力法求解 0/1 背包问题：1 )基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1 向量组成,可用子集数表示。 在搜索解空间树时， 深度优先遍历， 搜索每 一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得 到的装入总价值，

2、然后记录遍历过的最大价值。2)代码: #include #include using namespace std;#define N 100 / 最多可能物体数struct goods/ 物品结构体int sign;/ 物品序号int w; /物品重量int p; /物品价值aN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int max(int a,int b)return an-1)if(bestPcp&cw+ai.w=C)for (int k=0;kn;k+)Xk=cxk;/ 存储最优路径bestP=cp; return bestP;

3、cw=cw+ai.w;cp=cp+ai.p;cxi=1;/装入背包Force(i+1);cw=cw-ai.w;cp=cp-ai.p;cxi=0;/不装入背包Force(i+1);return bestP;int KnapSack1(int n,goods a,int C,int x)Force(0);return bestP;int mai n()goods bN;printf(物品种数 n:);scanf(%d,&n);/输入物品种数printf(背包容量 C:);scanf(%d,&C);/输入背包容量for (int i=0;in;i+)/输入物品i的重量w及其价值vprintf(物品

4、%d的重量 w%d及其价值 v%d:,i+1,i+1,i+1);sca nf(%d%d,&ai.w,&ai.p);bi=ai;int sum仁KnapSack1(n,a,C,X);调用蛮力法求0/1背包问题printf(蛮力法求解0/1背包问题:nX=);for(i=0;i n ;i+)coutXi ;/ 输出所求 Xn矩阵printf(装入总价值 dn,sum1);bestP=0,cp=0,cw=0; 恢复初始化3)复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：T(n )=O(2n)。2. 动态规划法求解0/1背包问题：1)基本思想：令V(i, j)表示在前i(1叮乞n)个物品中能够装

5、入容量为j(1乞j C)的背包中的物品的最大值，则可以得到如下动态函数:V(i,O) =V(O,j) =0V(i, j)，V(i1, j)(j wjmaxV (i 1, j ),V (i 1, j 一 Wj) + y 丸 j H wj按照下述方法来划分阶段：第一阶段，只装入前 1个物品，确定在 各种情况下的背包能够得到的最大价值； 第二阶段，只装入前2个物品， 确定在各种情况下的背包能够得到的最大价值；以此类推，直到第 n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最 大价值。2 )代码：#in clude#i ncludeusing n amespace std;#d

6、efine N 100/最多可能物体数struct goods/物品结构体int sign;/物品序号int w;/物品重量int p;/物品价值aN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int max(i nt a,i nt b)retur n ab?b:a;int n ,C,bestP=0,cp=0,cw=0;int XN,cxN;int VN10*N; for(i nt i=0;i=n ;i+)Vi0=0;for(i nt j=0;j=C;j+)V0j=0;for(i=1;i=n ;i+)int KnapSack2(int n

7、,goods a,int C,int x) /初始化第0列/初始化第0行/计算第i行，进行第i次迭代for(j=1;j=C;j+)if(j0;i_)if (VijVi-1j) xi-1=1; j=j-ai-1.w;xi-1=0; elsereturn Vn C; /返回背包取得的最大价值int mai n()goods bN;n:);输入物品种数C:);输入背包容量II输入物品i的重量w及其价值vprintf(”物品种数scan f(%d,&n); II prin tf(背包容量scan f(%d,&C); II for (in t i=0;i n;i+)printf(物品 d的重量 w%d及

8、其价值 v%d: ,i+1,i+1,i+1);scan f(%d%d,&ai.w, &ai.p);bi=ai;int sum2=K nap Sack2( n,a,C,X);调用动态规划法求 0/1背包问题printf(动态规划法求解 0/1背包问题:nX=);for(i=0;i n ;i+)coutXi ;II输出所求 Xn矩阵printf(装入总价值 %dn,sum2);for (i=0;i n ;i+)ai=bi;II 恢复aN顺序3)复杂度分析：动态规划法求解0I1背包问题的时间复杂度为：T(n) = O(n C)。3. 回溯法求解0/1背包问题：1) 基本思想：回溯法：为了避免生成那些

9、不可能产生最佳解的问题状态，要不断地利用限界函数 (bounding function) 来处死那些实际上不可能产生所 需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生 成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1 向量组成,可用子集数表示。 在搜索解空间树时， 只要其左儿子结点是一 个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进 入右子树搜索。2 )代码 :#include#include using namespace std; #define N 100 struct goods / int sign;/ 最多可能物体数 物

10、品结构体/ 物品序号int w;int p;aN;bool m(goods a,goods b) / 物品重量/ 物品价值return (a.p/a.w)(b.p/b.w);int max(int a,int b)return an-1) if(bestPcp)for (int k=0;kn;k+)Xk=cxk;/ 存储最优路径bestP=cp;return bestP;if(cw+ai.w=C)cw=cw+ai.w; cp=cp+ai.p; cxai.sign=1; / BackTrack(i+1); cw=cw-ai.w; cp=cp-ai.p;/ 进入左子树装入背包/ 回溯，进入右子树不

11、装入背包 cxai.sig n=0; / BackTrack(i+1); return bestP;int KnapSack3(int n,goods a,int C,int x)for(i nt i=0;i n;i+) xi=0; ai.sig n=i;将各物品按单位重量价值降序排列sort(a,a+n,m); BackTrack(O); return bestP; int mai n()goods bN;printf(物品种数 n:);scanf(%d,&n);/输入物品种数printf(背包容量 C:);scanf(%d,&C);/输入背包容量for (int i=0;in;i+)/输入

12、物品i的重量 w及其价值 vprintf(物品 d的重量 w%d及其价值 v%d: ,i+1,i+1,i+1);scan f(%d%d, &ai.w,&ai.p);bi=ai;int sum3=K nap Sack3( n,a,C,X);调用回溯法求 0/1 背包问题printf(回溯法求解0/1背包问题：nX=);for(i=0;i n ;i+)coutXi ;/输出所求 Xn矩阵printf(装入总价值 %dn,sum3);for (i=0;i n;i+)ai=bi;/ 恢复aN顺序3)复杂度分析：最不理想的情况下，回溯法求解 0/1背包问题的时间复杂度为:T(n) =O(2n)。由于其对

13、蛮力法进行优化后的算法， 其复杂度一般比蛮力 法要小。空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一个一维数组，即回溯法求解 0/1 背包问题的空间复杂度为 O(n)4. 分支限界法求解背包问题：1)基本思想：分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算 法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解 目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标 则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某 一目标函数值达到极大或极小的解，即在某种意义下的最优解。首先，要对输入数据进行预处理，将各物品依其单位重量价值从大 到小进行排

14、列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物 品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子 结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展 结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才 将它加入子集树和活结点优先队列。 当扩展到叶节点时为问题的最优值2) 代码:#include#includeusing namespace std;#define N 100 / 最多可能物体数struct goods / 物品结构体int sign; / 物品序号int w; / 物品

15、重量int p; / 物品价值aN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int max(int a,int b)return aHi/2.b) swap(Hi, Hi/2);elsedone = true;i = i/2;/ 堆中元素下移void mov_down(HEAP H, int n, int i)bool done = false; if(2*i)=n)while(!done & (i = 2*i) = n) if(i+1 Hi.b) i+; if(Hi/2.bHi.b) swap(Hi/2, Hi);elsedone =

16、 true;/ 往堆中插入结点void insert(HEAP H, HEAP x, int &n)n+;Hn = x; mov_up(H,n);/ 删除堆中结点 void del(HEAP H, int &n, int i) HEAP x, y;x = Hi; y = Hn;n -;if(i=x.b) mov_up(H,i);else mov_down(H, n, i);/ 获得堆顶元素并删除HEAP del_top(HEAP H, int &n)HEAP x = H1;del(H, n, 1); return x;/ 计算分支节点的上界void bound( KNAPNODE* node,

17、 int M, goods a, int n)int i = node-k; float w = node-w; float p = node-p; if(node-wM) / 物体重量超过背包载重量 node-b = 0; / 上界置为 0else while(w+ai.w=M)&(in)w += ai.w; / 计算背包已装入载重 p += ai+.p; /计算背包已装入价值if(ib = p + (M - w)*ai.p/ai.w;else node - b = p; / 用分支限界法实现 0/1 背包问题 int KnapSack4(int n,goods a,int C, int X

18、)int i, k = 0; / 堆中元素个数的计数器初始化为 0 int v;KNAPNODE *xnode, *ynode, *znode;/ 分配堆的存储空间记录物体的初始编号对物体按照价值重量比排序 / 建立父亲结点 初始化结点HEAP x, y, z, *heap; heap = new HEAPn*n; for( i=0; in; i+) ai.sign=i; /sort(a,a+n,m); / xnode = new KNAPNODE; for( i=0; is1i = false;xnode-p = 0; xnode-k = xnode-w =while(xnode-ks1yn

19、ode-k = true; ynode-w += aynode-k.w; ynode-p += aynode-k.p; ynode-k +; / bound(ynode, C, a, n); / y.b = ynode-b;y.p = ynode; insert(heap, y, k); / znode = new KNAPNODE; *znode = *xnode; / znode-k+; / bound(znode, C, a, n); / z.b = znode-b;z.p = znode; insert(heap, z, k); / delete xnode;x = del_top(h

20、eap, k); / 建立结点 y结点 x 的数据复制到结点 y/ 装入第 k 个物体/背包中物体重量累计/背包中物体价值累计搜索深度 +计算结点 y 的上界结点 y 按上界的值插入堆中 / 建立结点 z结点 x 的数据复制到结点 z 搜索深度 + 计算节点 z 的上界结点 z 按上界的值插入堆中获得堆顶元素作为新的父亲结点xnode = x.p;v = xno de-p;for( i=0; is1i)Xai.sig n =1 ;elseXai.sig n = 0;delete xno de;delete heap;return v;/返回背包中物体的价值/*测试以上算法的主函数*/int mai n()goods bN;printf(物品种数 n:);scanf(%d,&n);/输入物品种数prin