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

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

2、码：#include#includeusing 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;cw=cw+ai.w;cp=cp+ai.p

3、;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 main()(goods bN;printf(物品种数 n:);scanf(%d”,&n);/输入物品种数printf (-背包容量 C:);scanf(d,&C);输入背包容量for (int i=0;in;i+) /输入物品i的重量w及其价值v(printf(-物品d的重量 w%d及其价值 v%d:

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

5、法来划分阶段：第一阶段，只装入前1个物品，确定在 各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品， 确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最 if(jai-1.w)大价值。2)代码：#include #include using namespace #define N 100 struct goods intint大价值。2)代码：#include #include using namespace #define N 100 struct goods intintint aN; bool

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

7、int VN10*N;for(int i=0;i=n;i+)Vi0=0;for(int j=0;j=C;j+)V0j=0;for(i=1;i=n;i+)for(j=1;j0;i-) if (VijVi-1j) xi-1=1; j=j-ai-1.w;else xi-1=0;return VnC; /返回背包取得的最大价值int main()goods bN;printf(物品种数 n:);scanf(%d”,&n); /输入物品种数printf (-背包容量 C:);scanf(d，&C); /输入背包容量for (int i=0;in;i+) /输入物品i的重量w及其价值vprintf (-物

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

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

10、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;/回溯，进入右子树cxai.sign=0; /不装入背包BackTrac

11、k(i+1);return bestP;int KnapSack3(int n,goods a,int C,int x)for(int i=0;in;i+)xi=0;ai.sign=i;sort(a,a+n,m);/各物品按单位重量价值降序排列BackTrack(0);return bestP;int main()goods bN;printf(物品种数 n:);scanf(%d”,&n); /输入物品种数printf (-背包容量 C:);scanf(d，&C); /输入背包容量for (int i=0;in;i+)/输入物品i的重量w及其价值vprintf (-物品d 的重量 w%d及其价

12、值 v:%d: ，i+1,i+1,i+1);scanf(%d%d”,&ai.w,&ai.p);bi=ai;int sum3=KnapSack3(n,a,C,X);/调用回溯法求 0/1 背包问题printf(-回溯法求解0/1背包问题:nX=);for(i=0;in;i+)coutXi ;/输出所求 Xn矩阵printf(装入总价值 dn”,sum3);for (i=0;in;i+)ai=bi;/恢复aN顺序复杂度分析：最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为：T(n) O(2n)。由于其对蛮力法进行优化后的算法，其复杂度一般比蛮力法要小。空间复杂度：有n个物品，即最多递归n层

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

14、剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子 结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展 结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才 将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。代码：#include#includeusing 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

15、/b.w);int max(int a,int b)(return aHi/2.b) swap(Hi, Hi/2); else( done = 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);else( done = true;/往堆中插入结点void insert(HEAP H, HEAP x, int &n)(n+;Hn

16、 = 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, int M, goods a, int n)(int i = node-k;float w = node-w;floa

17、t 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)(/堆中元素个数的计数器初始化为0int i, k = 0;/堆中元素个数的计数器初始化为0int v;KNAPNODE *xnode, *yn

18、ode, *znode;HEAP x, y, z, *heap;/分配堆的存储空间heap = new HEAPn*n;/分配堆的存储空间for( i=0; in; i+)(记录物体的初始编号ai.sign=i;记录物体的初始编号/对物体按照价值重量比排序/建立父亲结点/对物体按照价值重量比排序/建立父亲结点/ 初始化结点xnode = new KNAPNODE;for( i=0; is1i = false;xnode-k = xnode-w = xnode-p = 0;while(xnode-ks1ynode-k= true;.w;ynode-p += aynode-k.p;/ynode-k

19、 +;/bound(ynode, C, a, n);/y.b = ynode-b;y.p = ynode;结点y结点y按上界的值插入堆中/建立结点z结点X的数据复制到结点z/搜索深度+计算节点z的上界znode = new KNAPNODE;*znode = *xnode;znode-k+;bound(znode, C, a, n);z.b = znode-b;z.p = znode;结点z结点z按上界的值插入堆中delete xnode;获得堆顶元素作为新的父亲结点x = del_top(heap, k);获得堆顶元素作为新的父亲结点xnode = x.p;v = xnode-p;for( i=0; is1i)Xai.sign =1 ;else(Xai.sign = 0;delete xnode;delete heap;return v;返回背包中物体的价值/*测试以上算法的主函数*/int main()(goods bN;printf(物品种数 n:);scanf(%d”,&n); /输入物品种数printf (-背包容量 C:);s