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

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

2、入总价值，然 后记录遍历过的最大价值。2）代码:#include<iostream>#include<algorithm>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 a<b?b:a;int n,C,bestP=0,cp=0,cw=0;int X

3、N,cxN;/* 蛮力法求解 0/1 背包问题 */int Force(int i)if(i>n-1)if(bestP<cp&&cw+ai.w<=C)for (int k=0;k<n;k+)Xk=cxk;/ 存储最优路径 bestP=cp; return bestP;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)

4、 Force(0);return bestP;int main()goods bN;printf(" 物品种数 n: "); scanf("%d",&n);/ 输入物品种数 printf(" 背包容量 C: ");3 / 22sea nf("%d", &C);输入背包容量for (int i=0;i<n;i+)输入物品i的重量w及其价值vprintf("物品 %d 的重量 w%d及其价值 v%d:",i+1,i+1,i+1);sea nf("%d%d",

5、&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+)coutv<Xivv" "/ 输出所求 Xn矩阵printf("装入总价值 %dn",sum1);bestP=0,cp=0,cw=0;/恢 恢复初始化3)复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：T(n) 0(2n)。2动态规划法求解0/1背包问题：1) 基本思想：令V(i,j)表示在前i(1 in)个

6、物品中能够装入容量为j(1 j C)的背包中的物品的最大值，则可以得到如下动态函数：V(i,0) V(0,j) 0V(i 1,j)(j wmaxV(i 1,j),V(i1,j w) v(j w)iii按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。2) 代码：#in clude<iostream>#in clude<algorithm>using n amesp

7、ace std;#define N 100最多可能物体数struct goods/物品结构体int sig n;物品序号int w;物品重量int p;物品价值aN;bool m(goods a,goods b)retur n (a.p/a.w)>(b.p/b.w);int max(int a,int b)return a<b?b:a;int n,C,bestP=0,cp=0,cw=0;int XN,cxN;int KnapSack2(int n,goods a,int C,int x)int VN10*N;for(int i=0;i<=n;i+)/ 初始化第 0 列Vi0=

8、0;for(int j=O;jv二C;j+) 初始化第 0 行V0j=0;for(i=1;i<=n;i+)/ 计算第 i 行，进行第 i 次迭代 for(j=1;j<=C;j+)if(j<ai-1.w)Vij=Vi-1j;elseVij=max(Vi-1j,Vi-1j-ai-1.w+ai-1.p);j=C;/ 求装入背包的物品for (i=n;i>0;i-)if (Vij>Vi-1j)xi-1=1; j=j-ai-1.w;elsexi-1=0;return VnC; / 返回背包取得的最大价值int main()goods bN;printf(" 物品种

9、数 n: ");scanf("%d",&n); / 输入物品种数printf(" 背包容量 C: ");scanf("%d",&C); / 输入背包容量for (int i=0;i<n;i+)/ 输入物品 i 的重量 w 及其价值 v printf("物品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);调用动态规划法

10、求0/1背包问题printf("动态规划法求解0/1背包问题:nX=");for(i=0;i <n ;i+)coutv<Xivv" "/ 输出所求 Xn矩阵printf("装入总价值 dn",sum2);for (i=0;i <n ;i+)ai=bi;/恢复aN顺序3) 复杂度分析：动态规划法求解0/1背包问题的时间复杂度为：T(n) O(n C)。3回溯法求解0/1背包问题：1) 基本思想：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用 限界函数(bounding function)来处死那些实际

11、上不可能产生所需解的活结点，以 减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组 成，可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点， 搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。2) 代码：#in clude<iostream>#include<algorithm>using namespace std;#define N 100/ 最多可能物体数 struct goods / 物品结构体int sign;/ 物品序号int w;/ 物品重量int

12、p;/ 物品价值aN;bool m(goods a,goods b)return (a.p/a.w)>(b.p/b.w);int max(int a,int b)return a<b?b:a;int n,C,bestP=0,cp=0,cw=0;int XN,cxN;int BackTrack(int i)9 / 223.曰 e+cbucbM 曰 e+MoHMoWRWV®、xov/vv 曰 e+Mg 七 宀CL4S q una) 宀-cbHCRS q型蚩sw迴>注Ex。"兰 X(+KUVKO艾茎一)O4McbvcRS q)七)(LUC_=一7Z 一 OLax

13、 4U-O4ur=e spooqu luDcoMoesdeuy 4£ 宀CL4S q una)二 土) MoeEoeH*<<kuo''u6_s.曰 ex。宀 w中柜<®冕回注d.曰ecbucbM 曰 eMoHMo 二 土) MoeEoeH*<<FL"U6_S.曰 ex。for(int i=0;i<n;i+)xi=0;ai.sign=i;sort(a,a+n,m);/ 将各物品按单位重量价值降序排列BackTrack(0);return bestP;int main()goods bN;printf("

14、物品种数 n: ");scanf("%d",&n);/ 输入物品种数printf(" 背包容量 C: ");sea nf("%d", &C);输入背包容量for (int i=0;i<n;i+)输入物品i的重量w及其价值vprintf("物品%d的重量w%d及其价值v%d:",i+1,i+1,i+1);seanf("%d%d",&ai.w,&ai.p);bi=ai;int sum3=KnapSack3(n,a,C,X);调用回溯法求0/1背包问题p

15、rintf(”回溯法求解0/1背包问题:nX=");for(i=0;i <n ;i+)coutv<Xivv" "/ 输出所求 Xn矩阵printf("装入总价值 %dn",sum3);for (i=0;i <n ;i+)ai=bi;/恢复aN顺序3)复杂度分析：最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为：T(n) 0(2 n)。由于其对蛮力法进行优化后的算法，其复杂度一般比蛮力法要 小。空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一个一维 数组，即回溯法求解0/1背包问题的空间复杂度为 0(n)。4分

16、支限界法求解背包问题：1)基本思想：分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一 般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解 空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条 件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极 小的解，即在某种意义下的最优解。首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进 行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值 加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点

17、是 可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子 结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活 结点优先队列。当扩展到叶节点时为问题的最优值。2)代码:#include<iostream>#include<algorithm>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

18、.p/b.w);int max(int a,int b)return a<b?b:a;int n,C,bestP=0,cp=0,cw=0;int XN,cxN;struct KNAPNODE/状犬态结构体bool s1N; / 当前放入物体int k;/ 搜索深度int b; / 价值上界int w; / 物体重量int p; / 物体价值;struct HEAP/堆元素结构体KNAPNODE *p;/结点数据int b;/ 所指结点的上界;/ 交换两个堆元素void swap(HEAP &a, HEAP &b)HEAP temp = a;a = b;b = temp;/

19、 堆中元素上移void mov_up(HEAP H, int i)bool done = false;if(i!=1)while(!done && i!=1) if(Hi.b>Hi/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<=n && Hi+1.b > H

20、i.b) i+;if(Hi/2.b<Hi.b)swap(Hi/2, Hi);elsedone = 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<=n)Hi = y;if(y.b>=x.b)mov_up(H,i);elsemov_down(H, n, i);/ 获得堆顶元素并删除HEAP del_top(HEAP H, i

21、nt &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;float p = node->p;if(node->w>M) / 物体重量超过背包载重量 node->b = 0; / 上界置为 0else while(w+ai.w<=M)&&(i<n)w += ai.w; / 计算背包已装入载重p += ai+.p;

22、 / 计算背包已装入价值 if(i<n)node->b = p + (M - w)*ai.p/ai.w;elsenode -> b = p;/ 用分支限界法实现 0/1 背包问题int KnapSack4(int n,goods a,int C, int X)int i, k = 0;/ 堆中元素个数的计数器初始化为 0int v;KNAPNODE *xnode, *ynode, *znode;HEAP x, y, z, *heap;heap = new HEAPn*n; / 分配堆的存储空间for( i=0; i<n; i+)ai.sign=i; / 记录物体的初始编

23、号sort(a,a+n,m); / 对物体按照价值重量比排序 xnode = new KNAPNODE; / 建立父亲结点for( i=0; i<n; i+)/ 初始化结点xnode->s1i = false;xnode->k = xnode->w = xnode->p = 0;while(xnode->k<n) ynode = new KNAPNODE;/ 建立结点 y*ynode = *xnode;/ 结点 x 的数据复制到结点yynode->s1ynode->k = true;/ 装入第 k 个物体 ynode->w += ay

24、node->k.w;/ 背包中物体重量累计 ynode->p += aynode->k.p;/ 背包中物体价值累计ynode->k +; / 搜索深度 +bound(ynode, C, a, n); / 计算结点 y 的上界 y.b = ynode->b;y.p = ynode;insert(heap, y, k);/ 结点 y 按上界的值插入堆中 znode = newKNAPNODE; / 建立结点 z*znode = *xnode; / 结点 x 的数据复制到结点 zznode->k+;/ 搜索深度 +bound(znode, C, a, n); /

25、计算节点 z 的上界z.b = znode->b;z.p = znode;insert(heap, z, k);/ 结点 z 按上界的值插入堆中 delete xnode;x = del_top(heap, k); / 获得堆顶元素作为新的父亲结点 xnode = x.p;v = xnode->p;for( i=0; i<n; i+)/ 取装入背包中物体在排序前的序号 if(xnode->s1i)Xai.sign =1 ;elseXai.sign = 0;delete xnode;delete heap;return v;/ 返回背包中物体的价值/* 测试以上算法的主函数 */int main()goods bN;printf(" 物品种数 n: