2023年8月1日发(作者：)

一、实验内容：二、所用算法的基本思想及复杂度分析：入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。注：0/1背包问题：给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何使选择装入背包内的物品，使得装

12016

2

81

421.蛮力法求解0/1背包问题：1）基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。2）代码:#include#includeusing namespace std;#define N 100//最多可能物体数struct goods//物品结构体{int sign;//物品序号int w;//物品重量int p;//物品价值}a[N];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(bestP

12016

2

81

422.动态规划法求解0/1背包问题：1）基本思想：}int KnapSack1(int n,goods a[],int C,int x[]){Force(0);return bestP;}int main(){goods b[N];printf("物品种数n: ");scanf("%d",&n);//输入物品种数printf("背包容量C: ");scanf("%d",&C);//输入背包容量for (int i=0;i

",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];}int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题printf("蛮力法求解0/1背包问题:nX=[ ");for(i=0;i #include using namespace std; #define N 100//最多可能物体数 struct goods//物品结构体 }a[N]; bool m(goods a,goods b) { return (a.p/a.w)>(b.p/b.w); } int max(int a,int b) { return a

12016

2

81

42V(i,0)V(0,j)0阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个 for(j=1;j<=C;j++)//初始化第0行令V(i,j)表示在前i(1in)个物品中能够装入容量为j(1jC)的V(i1,j)(jwi)V(i,j)V(i1,j),V(i1,jwi)vi(jwi)max//计算第i行，进行第i次迭代 }

3）复杂度分析: } int main() { goods b[N]; printf("物品种数n: "); scanf("%d",&n);//输入物品种数 printf("背包容量C: "); scanf("%d",&C);//输入背包容量 for (int i=0;i0;i--) { if (V[i][j]>V[i-1][j]){ x[i-1]=1; j=j-a[i-1].w; } elsex[i-1]=0; } return V[n][C];//返回背包取得的最大价值动态规划法求解0/1背包问题的时间复杂度为：T(n)O(nC)。 { printf("物品%d的重量w[%d]及其价值v[%d]: ",i+1,i+1,i+1); if(j

12016

2

81

423.回溯法求解0/1背包问题：1）基本思想：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断 bestP=cp; } return bestP; } if(cw+a[i].w<=C){ { int sign;//物品序号 int w;//物品重量 int p;//物品价值 #include #include using namespace std; #define N 100//最多可能物体数 struct goods//物品结构体 }a[N]; 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(bestP

12016

2

81

42地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 2）代码:X[k]=cx[k];//存储最优路径 BackTrack(i+1); cw=cw-a[i].w; cp=cp-a[i].p; cw=cw+a[i].w; cp=cp+a[i].p; cx[a[i].sign]=1;//装入背包//进入左子树//回溯，进入右子树 BackTrack(i+1); return bestP; } int KnapSack3(int n,goods a[],int C,int x[]) { for(int i=0;i

12016

2

81

42力法要小。空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一T(n)O(2n)。由于其对蛮力法进行优化后的算法，其复杂度一般比蛮

12016

2

81

42个一维数组，即回溯法求解0/1背包问题的空间复杂度为O(n)。4.分支限界法求解背包问题：1）基本思想：分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。2）代码:#include#includeusing namespace std;#define N 100//最多可能物体数struct goods//物品结构体{int sign;//物品序号int w;//物品重量int p;//物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(int a,int b){return a

12016

2

81

42};struct HEAP//堆元素结构体{KNAPNODE *p;//结点数据int b; //所指结点的上界};//交换两个堆元素void swap(HEAP &a, HEAP &b){HEAP temp = a;a = b;b = temp;}//堆中元素上移void mov_up(HEAP H[], int i){bool done = false;if(i!=1){while(!done && i!=1){if(H[i].b>H[i/2].b){swap(H[i], H[i/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<=n && H[i+1].b > H[i].b){i++;}if(H[i/2].b

12016

2

81

42}//往堆中插入结点void insert(HEAP H[], HEAP x, int &n){n++;H[n] = x;mov_up(H,n);}//删除堆中结点void del(HEAP H[], int &n, int i){HEAP x, y;x = H[i]; y = H[n];n --;if(i<=n){H[i] = y;if(y.b>=x.b){mov_up(H,i);}else{mov_down(H, n, i);}}}//获得堆顶元素并删除HEAP del_top(HEAP H[], int &n){HEAP x = H[1];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; // 上界置为0}else{while((w+a[i].w<=M)&&(i

w += a[i].w; // 计算背包已装入载重p += a[i++].p; // 计算背包已装入价值}}if(ib = p + (M - w)*a[i].p/a[i].w;}else{node -> b = p;}

12016

2

81

42}//用分支限界法实现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 HEAP[n*n]; // 分配堆的存储空间for( i=0; is1[i] = false;}xnode->k = xnode->w = xnode->p = 0;while(xnode->ks1[ynode->k] = true; // 装入第k个物体ynode->w += a[ynode->k].w; // 背包中物体重量累计ynode->p += a[ynode->k].p; // 背包中物体价值累计ynode->k ++; // 搜索深度++bound(ynode, C, a, n); // 计算结点y的上界y.b = ynode->b;y.p = ynode;insert(heap, y, k); //结点y按上界的值插入堆中znode = new KNAPNODE; // 建立结点z*znode = *xnode; //结点x的数据复制到结点zznode->k++; // 搜索深度++bound(znode, C, a, n); //计算节点z的上界z.b = znode->b;z.p = znode;insert(heap, z, k); //结点z按上界的值插入堆中delete xnode; 分支限界法求解0/1背包问题的时间复杂度为：T(n)O(2n)。}/*测试以上算法的主函数*/int main(){goods b[N];printf("物品种数n: ");scanf("%d",&n);//输入物品种数printf("背包容量C: ");scanf("%d",&C);//输入背包容量for (int i=0;i

",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];}int sum4=KnapSack4(n,a,C,X);//调用分支限界法求0/1背包问题printf("分支限界法求解0/1背包问题:nX=[ ");for(i=0;i

12016

2

81

42}v = xnode->p;for( i=0; is1[i]){X[a[i].sign] =1 ;}else{X[a[i].sign] = 0;}}delete xnode;delete heap;return v; //返回背包中物体的价值x = del_top(heap, k); //获得堆顶元素作为新的父亲结点xnode = x.p;五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训： 相同的数据，求相同同的问题，用不同的方法，得到的结果，所得结果

正式所求问题的最优解，所编程序是正确的。1.本实验中4种算法要用同一个主函数调用，由于背包容量、物品、解向

12016

2

81

42量等变量都是以全局变量定义的，每次调用一种算法之前，必须要看这些重要的变量值是否因上一个算法的调用而发生了改变，如发生改变，则需将其改回原值，使得各种算法之间互不影响。2.在本实验中，各种算法因申请存储空间等原因，运行时间的排序不可能与其时间复杂度的一致，甚至可能会有很大差别，又不可能输入大量数据进行各种算法的测试，所以没有求各算法的运行时间并进行比较。即各算法的运行时间受较多因素影响，较小数据量时与算法时间复杂度无相关性，比较是没有意义的

2023年8月1日发(作者：)

一、实验内容：二、所用算法的基本思想及复杂度分析：入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。注：0/1背包问题：给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何使选择装入背包内的物品，使得装

12016

2

81

421.蛮力法求解0/1背包问题：1）基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。2）代码:#include#includeusing namespace std;#define N 100//最多可能物体数struct goods//物品结构体{int sign;//物品序号int w;//物品重量int p;//物品价值}a[N];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(bestP

12016

2

81

422.动态规划法求解0/1背包问题：1）基本思想：}int KnapSack1(int n,goods a[],int C,int x[]){Force(0);return bestP;}int main(){goods b[N];printf("物品种数n: ");scanf("%d",&n);//输入物品种数printf("背包容量C: ");scanf("%d",&C);//输入背包容量for (int i=0;i

",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];}int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题printf("蛮力法求解0/1背包问题:nX=[ ");for(i=0;i #include using namespace std; #define N 100//最多可能物体数 struct goods//物品结构体 }a[N]; bool m(goods a,goods b) { return (a.p/a.w)>(b.p/b.w); } int max(int a,int b) { return a

12016

2

81

42V(i,0)V(0,j)0阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个 for(j=1;j<=C;j++)//初始化第0行令V(i,j)表示在前i(1in)个物品中能够装入容量为j(1jC)的V(i1,j)(jwi)V(i,j)V(i1,j),V(i1,jwi)vi(jwi)max//计算第i行，进行第i次迭代 }

3）复杂度分析: } int main() { goods b[N]; printf("物品种数n: "); scanf("%d",&n);//输入物品种数 printf("背包容量C: "); scanf("%d",&C);//输入背包容量 for (int i=0;i0;i--) { if (V[i][j]>V[i-1][j]){ x[i-1]=1; j=j-a[i-1].w; } elsex[i-1]=0; } return V[n][C];//返回背包取得的最大价值动态规划法求解0/1背包问题的时间复杂度为：T(n)O(nC)。 { printf("物品%d的重量w[%d]及其价值v[%d]: ",i+1,i+1,i+1); if(j

12016

2

81

423.回溯法求解0/1背包问题：1）基本思想：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断 bestP=cp; } return bestP; } if(cw+a[i].w<=C){ { int sign;//物品序号 int w;//物品重量 int p;//物品价值 #include #include using namespace std; #define N 100//最多可能物体数 struct goods//物品结构体 }a[N]; 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(bestP

12016

2

81

42地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 2）代码:X[k]=cx[k];//存储最优路径 BackTrack(i+1); cw=cw-a[i].w; cp=cp-a[i].p; cw=cw+a[i].w; cp=cp+a[i].p; cx[a[i].sign]=1;//装入背包//进入左子树//回溯，进入右子树 BackTrack(i+1); return bestP; } int KnapSack3(int n,goods a[],int C,int x[]) { for(int i=0;i

12016

2

81

42力法要小。空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一T(n)O(2n)。由于其对蛮力法进行优化后的算法，其复杂度一般比蛮

12016

2

81

42个一维数组，即回溯法求解0/1背包问题的空间复杂度为O(n)。4.分支限界法求解背包问题：1）基本思想：分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。2）代码:#include#includeusing namespace std;#define N 100//最多可能物体数struct goods//物品结构体{int sign;//物品序号int w;//物品重量int p;//物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(int a,int b){return a

12016

2

81

42};struct HEAP//堆元素结构体{KNAPNODE *p;//结点数据int b; //所指结点的上界};//交换两个堆元素void swap(HEAP &a, HEAP &b){HEAP temp = a;a = b;b = temp;}//堆中元素上移void mov_up(HEAP H[], int i){bool done = false;if(i!=1){while(!done && i!=1){if(H[i].b>H[i/2].b){swap(H[i], H[i/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<=n && H[i+1].b > H[i].b){i++;}if(H[i/2].b

12016

2

81

42}//往堆中插入结点void insert(HEAP H[], HEAP x, int &n){n++;H[n] = x;mov_up(H,n);}//删除堆中结点void del(HEAP H[], int &n, int i){HEAP x, y;x = H[i]; y = H[n];n --;if(i<=n){H[i] = y;if(y.b>=x.b){mov_up(H,i);}else{mov_down(H, n, i);}}}//获得堆顶元素并删除HEAP del_top(HEAP H[], int &n){HEAP x = H[1];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; // 上界置为0}else{while((w+a[i].w<=M)&&(i

w += a[i].w; // 计算背包已装入载重p += a[i++].p; // 计算背包已装入价值}}if(ib = p + (M - w)*a[i].p/a[i].w;}else{node -> b = p;}

12016

2

81

42}//用分支限界法实现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 HEAP[n*n]; // 分配堆的存储空间for( i=0; is1[i] = false;}xnode->k = xnode->w = xnode->p = 0;while(xnode->ks1[ynode->k] = true; // 装入第k个物体ynode->w += a[ynode->k].w; // 背包中物体重量累计ynode->p += a[ynode->k].p; // 背包中物体价值累计ynode->k ++; // 搜索深度++bound(ynode, C, a, n); // 计算结点y的上界y.b = ynode->b;y.p = ynode;insert(heap, y, k); //结点y按上界的值插入堆中znode = new KNAPNODE; // 建立结点z*znode = *xnode; //结点x的数据复制到结点zznode->k++; // 搜索深度++bound(znode, C, a, n); //计算节点z的上界z.b = znode->b;z.p = znode;insert(heap, z, k); //结点z按上界的值插入堆中delete xnode; 分支限界法求解0/1背包问题的时间复杂度为：T(n)O(2n)。}/*测试以上算法的主函数*/int main(){goods b[N];printf("物品种数n: ");scanf("%d",&n);//输入物品种数printf("背包容量C: ");scanf("%d",&C);//输入背包容量for (int i=0;i

",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];}int sum4=KnapSack4(n,a,C,X);//调用分支限界法求0/1背包问题printf("分支限界法求解0/1背包问题:nX=[ ");for(i=0;i

12016

2

81

42}v = xnode->p;for( i=0; is1[i]){X[a[i].sign] =1 ;}else{X[a[i].sign] = 0;}}delete xnode;delete heap;return v; //返回背包中物体的价值x = del_top(heap, k); //获得堆顶元素作为新的父亲结点xnode = x.p;五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训： 相同的数据，求相同同的问题，用不同的方法，得到的结果，所得结果

正式所求问题的最优解，所编程序是正确的。1.本实验中4种算法要用同一个主函数调用，由于背包容量、物品、解向

12016

2

81

42量等变量都是以全局变量定义的，每次调用一种算法之前，必须要看这些重要的变量值是否因上一个算法的调用而发生了改变，如发生改变，则需将其改回原值，使得各种算法之间互不影响。2.在本实验中，各种算法因申请存储空间等原因，运行时间的排序不可能与其时间复杂度的一致，甚至可能会有很大差别，又不可能输入大量数据进行各种算法的测试，所以没有求各算法的运行时间并进行比较。即各算法的运行时间受较多因素影响，较小数据量时与算法时间复杂度无相关性，比较是没有意义的