0-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。

问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。

二、回溯法步骤思想描述：0-1背包问题是子集选取问题。

0-1 背包问题的解空间可以用子集树表示。

在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。

当右子树中有可能含有最优解时，才进入右子树搜索。

否则，将右子树剪去。

设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。

当cp+r<=bestp时，可剪去右子树。

计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。

例如：对于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。

分支界限方法是一种用于解决优化问题的算法。

在动态规划算法中，分支界限方法被广泛应用于解决01背包问题。

01背包问题是一个经典的动态规划问题，其解题步骤如下：1. 确定问题：首先需要明确01背包问题的具体描述，即给定一组物品和一个背包，每个物品有自己的价值和重量，要求在不超过背包容量的情况下，选取尽可能多的物品放入背包，使得背包中物品的总价值最大。

2. 列出状态转移方程：对于01背包问题，可以通过列出状态转移方程来描述问题的求解过程。

假设dp[i][j]表示在前i个物品中，背包容量为j时能够获得的最大价值，则状态转移方程可以表示为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])3. 初始化边界条件：在动态规划中，需要对状态转移方程进行初始化，一般情况下，dp数组的第一行和第一列需要单独处理。

对于01背包问题，可以初始化dp数组的第一行和第一列为0。

4. 利用分支界限方法优化：针对01背包问题，可以使用分支界限方法来优化动态规划算法的效率。

分支界限方法采用广度优先搜索的思想，在每一步选择最有希望的分支，从而减少搜索空间，提高算法的效率。

5. 实际解题步骤：根据上述步骤，实际解决01背包问题的步骤可以概括为：确定问题，列出状态转移方程，初始化边界条件，利用分支界限方法优化，最终得到问题的最优解。

分支界限方法在解决01背包问题时起到了重要的作用，通过合理的剪枝策略，可以有效地减少动态规划算法的时间复杂度，提高问题的求解效率。

分支界限方法也可以应用于其他优化问题的求解过程中，在算法设计和实现中具有重要的理论和实际意义。

在实际应用中，分支界限方法需要根据具体问题进行灵活选择和调整，结合动态规划和剪枝策略，以便更好地解决各类优化问题。

掌握分支界限方法对于解决复杂问题具有重要的意义，也是算法设计和优化的关键技术之一。

分支界限方法在解决01背包问题的过程中，具有重要的作用。

01背包各种算法代码实现总结（穷举，贪⼼，动态，递归，回溯，分⽀限界）2020-05-22所有背包问题实现的例⼦都是下⾯这张图01背包实现之——穷举法：1.我的难点：（1）在⽤穷举法实现代码的时候，我⾃⼰做的时候认为最难的就是怎么将那么多种情况表⽰出来，⼀开开始想⽤for循环进⾏多次嵌套，但是太⿇烦，⽽且还需要不断的进⾏各种标记。

我现在的⽔平实在太菜，然后就在⼀篇中看到⼀个特别巧妙的枚举算法,如下所⽰：int fun(int x[n]){int i;for(i=0;i<n;i++)if(x[i]!=1) {x[i]=1; return;}//从遇到的第⼀位开始，若是0，将其变成1，然后结束for循环，得到⼀种解法else x[i]=0;return;//从第⼀位开始，若是1，将其变成0，然后继续循环，若再循环的时候遇到0，则将其变为1，结束循环。

得到另⼀种解法。

} 虽然我现在也不知道为什么会这样，但是确实是个很好的规律，找到这个规律后，就可以很轻松的⾃⼰写出各种排列情况，以后遇到排列的问题，就⽤这个⽅法。

语⾔不好描述，上图⽚演⽰（是歪的，凑活看吧。

）：（2）算法思想：x[i]的值为0/1，即选或者不选w[i]的值表⽰商品i的重量v[i]的值表⽰商品的价值所以这个算法最核⼼的公式就是tw=x[1]*w[1]+x[2]*w[2]+.......+x[n]*w[n]tv=x[1]*w[1]+x[2]*v[2]+......+x[n]*v[n]tv1:⽤于存储当前最优解limit:背包容量如果 tw<limit&&tv>tv1 则可以找到最优解2.代码实现（借鉴）#include<stdio.h>#include<iostream>using namespace std;#define n 4void possible_solution(int x[n]){int i;for(i=0;i<4;i++) //n=4,有2^4-1种解法if(x[i]!=1){x[i]=1;return; //从遇到的第⼀位开始，若是0，将其变成1，然后结束循环，得到⼀种解法}elsex[i]=0;return;//从第⼀位开始，若是1，将其变成0，然后继续循环，若再循环的时候遇到0，则将其变为1，结束循环。

分支限界法求0-1背包问题实验程序以及代码（C++）本程序中（规定物品数量为3，背包容量为30，输入为6个数，前3个为物品重量，后3个数为物品价值）：代码：#include<iostream>#include<stack>using namespace std;#define N 100classHeapNode //定义HeapNode结点类{public:doubleupper,price,weight; //upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量int level,x[N]; //活节点在子集树中所处的层序号};double MaxBound(int i);double Knap();void AddLiveNode(double up,double cp,double cw,bool ch,int level);stack<HeapNode>High; //最大队Highdouble w[N],p[N]; //把物品重量和价值定义为双精度浮点数double cw,cp,c=30; //cw为当前重量，cp为当前价值，定义背包容量为30int n=3; //货物数量为3int main(){cout<<"请按顺序输入3个物品的重量：（按回车键区分每个物品的重量）"<<endl;int i;for(i=1;i<=n;i++)cin>>w[i]; //输入3个物品的重量cout<<"请按顺序输入3个物品的价值：（按回车键区分每个物品的价值）"<<endl;for(i=1;i<=n;i++)cin>>p[i]; //输入3个物品的价值cout<<"最大价值为：";cout<<Knap()<<endl; //调用knap函数输出最大价值return 0;}double MaxBound(int j) //MaxBound函数求最大上界{doubleleft=c-cw,b=cp; //剩余容量和价值上界while(j<=n&&w[j]<=left) //以物品单位重量价值递减装填剩余容量{left-=w[j];b+=p[j];j++;}if(j<=n)b+=p[j]/w[j]*left; //装填剩余容量装满背包return b;}void AddLiveNode(double up,double cp,double cw,bool ch,int lev)//将一个新的活结点插入到子集数和最大堆High中{HeapNode be;be.upper=up;be.price=cp;be.weight=cw;be.level=lev;if(lev<=n)High.push(be); //调用stack头文件的push函数}double Knap() //优先队列分支限界法，返回最大价值，bestx返回最优解{ int i=1; cw=cp=0; doublebestp=0,up=MaxBound(1); //调用MaxBound求出价值上界，best为最优值while(1) //非叶子结点{ double wt=cw+w[i];if(wt<=c) //左儿子结点为可行结点{ if(cp+p[i]>bestp) bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=MaxBound(i+1);if(up>=bestp) //右子数可能含最优解AddLiveNode(up,cp,cw,false,i+1);if(High.empty()) return bestp;HeapNode node=High.top(); //取下一扩展结点High.pop(); cw=node.weight; cp=node.price; up=node.upper; i=node.level;}}输出结果为：。

（C++）分⽀限界法求解背包问题1.beibao.h⽂件代码如下：#ifndef BEIBAO_H#define BEIBAO_H#include <math.h>//⼦空间中节点类型class BBnode{public:BBnode* parent; //⽗节点bool leftChild; //左⼉⼦节点标志BBnode(BBnode* par,bool ch){parent=par;leftChild=ch;}BBnode(){}};class HeapNode {public:BBnode* liveNode; // 活结点double upperProfit; //结点的价值上界double profit; //结点所相应的价值double weight; //结点所相应的重量int level; // 活结点在⼦集树中所处的层次号//构造⽅法HeapNode(BBnode* node, double up, double pp , double ww,int lev){liveNode = node;upperProfit = up;profit = pp;weight = ww;level = lev;}HeapNode(){}int compareTo(HeapNode o) {double xup =o.upperProfit;if(upperProfit < xup)return -1;if(upperProfit == xup)return 0;elsereturn 1;}};class Element {public:int id;double d;Element(){}Element(int idd,double dd){id=idd;d=dd;}int compareTo(Element x){double xd=x.d;if(d<xd)return -1;if(d==xd)return 0;return 1;}bool equals(Element x){return d==x.d;}};class MaxHeap{public:HeapNode *nodes;int nextPlace;int maxNumber;MaxHeap(int n){maxNumber = pow((double)2,(double)n);nextPlace = 1;//下⼀个存放位置nodes = new HeapNode[maxNumber];}MaxHeap(){}void put(HeapNode node){nodes[nextPlace] = node;nextPlace++;heapSort(nodes);}HeapNode removeMax(){HeapNode tempNode = nodes[1];nextPlace--;nodes[1] = nodes[nextPlace];heapSort(nodes);return tempNode;}void heapAdjust(HeapNode * nodes,int s,int m){HeapNode rc = nodes[s];for(int j=2*s;j<=m;j*=2){if(j<m&&nodes[j].upperProfit<nodes[j+1].upperProfit)++j;if(!(rc.upperProfit<nodes[j].upperProfit))break;nodes[s] = nodes[j];s = j;}nodes[s] = rc;}void heapSort(HeapNode * nodes){for(int i=(nextPlace-1)/2;i>0;--i){heapAdjust(nodes,i,nextPlace-1);}}} ;#endif2.测试代码#include <iostream>using namespace std;//⼦空间中节点类型#include "beibao.h"double c=30;const int n=3;double *w;double *p;double cw;double cp;int *bestX;MaxHeap * heap;//上界函数bound计算结点所相应价值的上界double bound(int i){double cleft=c-cw;double b=cp;while(i<=n&&w[i]<=cleft){cleft=cleft-w[i];b=b+p[i];i++;}//装填剩余容量装满背包if(i<=n)b=b+p[i]/w[i]*cleft;return b;}//addLiveNode将⼀个新的活结点插⼊到⼦集树和优先队列中void addLiveNode(double up,double pp,double ww,int lev,BBnode* par,bool ch){ //将⼀个新的活结点插⼊到⼦集树和最⼤堆中BBnode *b=new BBnode(par,ch);HeapNode node =HeapNode(b,up,pp,ww,lev);heap->put(node);}double MaxKnapsack(){//优先队列式分⽀限界法，返回最⼤价值，bestx返回最优解BBnode * enode=new BBnode();int i=1;double bestp=0;//当前最优值double up=bound(1);//当前上界while(i!=n+1){//⾮叶⼦结点//检查当前扩展结点的左⼉⼦⼦结点double wt=cw+w[i];if(wt<=c){if(cp+p[i]>bestp)bestp=cp+p[i];addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);}up=bound(i+1);if(up>=bestp)addLiveNode(up,cp,cw,i+1,enode,false);HeapNode node =heap->removeMax();enode=node.liveNode;cw=node.weight;cp=node.profit;up=node.upperProfit;i=node.level;}for(int j=n;j>0;j--){bestX[j]=(enode->leftChild)?1:0;enode=enode->parent;}return cp;}double knapsack(double *pp,double *ww,double cc,int *xx){//返回最⼤值，bestX返回最优解c=cc;//n=sizeof(pp)/sizeof(double);//定义以单位重量价值排序的物品数组Element *q=new Element[n];double ws=0.0;double ps=0.0;for(int i=0;i<n;i++){q[i]=Element(i+1,pp[i+1]/ww[i+1]);ps=ps+pp[i+1];ws=ws+ww[i+1];}if(ws<=c){return ps;}p=new double[n+1];w=new double[n+1];for(int i=0;i<n;i++){p[i+1]=pp[q[i].id];w[i+1]=ww[q[i].id];}cw=0.0;cp=0.0;bestX = new int[n+1];heap = new MaxHeap(n);double bestp = MaxKnapsack();for(int j=0;j<n;j++)xx[q[j].id]=bestX[j+1];return bestp;}void main(){w=new double[4];w[1]=16;w[2]=15;w[3]=15;p=new double[4];p[1]=45;p[2]=25;p[3]=25;int *x = new int[4];double m = knapsack(p,w,c,x);cout<<"*****分⽀限界法*****"<<endl;cout<<"*****物品个数：n="<<n<<endl;cout<<"*****背包容量：c="<<c<<endl;cout<<"*****物品重量数组：w= {"<<w[3]<<" "<<w[1]<<" "<<w[2]<<"}"<<endl; cout<<"*****物品价值数组：v= {"<<p[3]<<" "<<p[1]<<" "<<p[2]<<"}"<<endl; cout<<"*****最优值：="<<m<<endl;cout<<"*****选中的物品是:";for(int i=1;i<=3;i++)cout<<x[i]<<" ";cout<<endl;}3.测试结果：*****分⽀限界法**********物品个数：n=3*****背包容量：c=30*****物品重量数组：w= {15 16 15} *****物品价值数组：v= {25 45 25} *****最优值：=50*****选中的物品是:0 1 1。

分⽀限界法解决01背包问题1. 问题描述设有n个物体和⼀个背包,物体i的重量为wi价值为pi ,背包的载荷为M, 若将物体i（1<= i <=n）装⼊背包,则有价值为pi . ⽬标是找到⼀个⽅案, 使得能放⼊背包的物体总价值最⾼.设N=3, W=(16,15,15), P=(45,25,25), C=30（背包容量）2. 队列式分⽀限界法可以通过画分⽀限界法状态空间树的搜索图来理解具体思想和流程每⼀层按顺序对应⼀个物品放⼊背包（1）还是不放⼊背包（0）步骤：①⽤⼀个队列存储活结点表，初始为空② A为当前扩展结点，其⼉⼦结点B和C均为可⾏结点，将其按从左到右顺序加⼊活结点队列，并舍弃A。

③按FIFO原则，下⼀扩展结点为B，其⼉⼦结点D不可⾏，舍弃；E可⾏，加⼊。

舍弃B④ C为当前扩展结点，⼉⼦结点F、G均为可⾏结点，加⼊活结点表，舍弃C⑤扩展结点E的⼉⼦结点J不可⾏⽽舍弃；K为可⾏的叶结点，是问题的⼀个可⾏解，价值为45⑥当前活结点队列的队⾸为F, ⼉⼦结点L、M为可⾏叶结点，价值为50、25⑦ G为最后⼀个扩展结点，⼉⼦结点N、O均为可⾏叶结点，其价值为25和0⑧活结点队列为空，算法结束，其最优值为50注：活结点就是不可再进⾏扩展的节点，也就是两个⼉⼦还没有全部⽣成的节点3. 优先队列式分⽀限界法3.1 以活结点价值为优先级准则步骤：①⽤⼀个极⼤堆表⽰活结点表的优先队列，其优先级定义为活结点所获得的价值。

初始为空。

②由A开始搜索解空间树，其⼉⼦结点B、C为可⾏结点，加⼊堆中，舍弃A。

③B获得价值45，C为0. B为堆中价值最⼤元素，并成为下⼀扩展结点。

④ B的⼉⼦结点D是不可⾏结点，舍弃。

E是可⾏结点，加⼊到堆中。

舍弃B。

⑤ E的价值为45，是堆中最⼤元素，为当前扩展结点。

⑥ E的⼉⼦J是不可⾏叶结点，舍弃。

K是可⾏叶结点，为问题的⼀个可⾏解价值为45。

⑦继续扩展堆中唯⼀活结点C，直⾄存储活结点的堆为空，算法结束。

以下是使用C语言实现01背包问题的回溯法代码：```c#include <stdio.h>#include <stdlib.h>// 初始化背包struct knapsack {int maxWeight; // 背包最大承重int *items; // 物品数组int n; // 物品数量};// 定义物品重量、价值和数量int weights[] = {2, 2, 6, 5, 4};int values[] = {6, 3, 5, 4, 6};int quantities[] = {3, 2, 2, 1, 1};// 初始化背包最大承重和当前承重int maxWeight = 10;int currentWeight = 0;// 初始化最大价值为0int maxValue = 0;// 遍历物品数组void traverseItems(struct knapsack *knapsack, int index) { // 对于每个物品，遍历其数量for (int i = 0; i < knapsack->quantities[index]; i++) {// 如果当前物品可以放入背包装且当前承重不超过背包最大承重，计算放入该物品后的总价值，并更新最大价值if (currentWeight + weights[index] <= knapsack->maxWeight) {int currentValue = values[index] * knapsack->quantities[index];if (currentValue > maxValue) {maxValue = currentValue;}}// 回溯，将当前物品从背包装中移除，递归地尝试下一个物品knapsack->quantities[index]--;if (index < knapsack->n - 1) {traverseItems(knapsack, index + 1);}knapsack->quantities[index]++; // 恢复物品数量，以便下次遍历尝试放入其他物品}}// 主函数int main() {// 初始化背包装和物品数组struct knapsack knapsack = {maxWeight, weights, 5};knapsack.items = (int *)malloc(sizeof(int) * knapsack.n);for (int i = 0; i < knapsack.n; i++) {knapsack.items[i] = values[i] * quantities[i]; // 根据价值和数量计算物品价值，并存储在物品数组中}knapsack.n = quantities[4]; // 由于最后一个物品的数量为1，因此只需遍历前n-1个物品即可得到所有可能的结果// 使用回溯法求解01背包问题，返回最大价值traverseItems(&knapsack, 0);printf("The maximum value is %d.\n", maxValue);free(knapsack.items); // 释放内存空间return 0;}```希望以上信息能帮助到你。

一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。

注：0/1背包问题：给定种物品和一个容量为的背包，物品的重n C i 量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装i w i v 入背包中的物品的总价值最大。

其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析：1.蛮力法求解0/1背包问题：1）基本思想：对于有n 种可选物品的0/1背包问题，其解空间由长度为n 的0-1向量组成,可用子集数表示。

在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。

2）代码:#include<iostream>#include<algorithm>using 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<b?b:a;}int n,C,bestP=0,cp=0,cw=0;int X[N],cx[N];/*蛮力法求解0/1背包问题*/int Force(int i){if(i>n-1){if(bestP<cp&&cw+a[i].w<=C){for (int k=0;k<n;k++)X[k]=cx[k];//存储最优路径bestP=cp;}return bestP;}cw=cw+a[i].w;cp=cp+a[i].p;cx[i]=1;//装入背包Force(i+1);cw=cw-a[i].w;cp=cp-a[i].p;cx[i]=0;//不装入背包Force(i+1);return bestP;}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<n;i++)//输入物品i 的重量w 及其价值v {printf("物品%d 的重量w[%d]及其价值v[%d]:",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<n;i++)cout<<X[i]<<" ";//输出所求X[n]矩阵printf("]装入总价值%d\n",sum1);bestP=0,cp=0,cw=0;//恢复初始化}3）复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：。

分⽀限界法解决01背包问题 分⽀限界法和之前讲的回溯法有⼀点相似，两者都是在问题的解的空间上搜索问题的解。

但是两者还是有⼀些区别的，回溯法是求解在解的空间中的满⾜的所有解，分⽀限界法则是求解⼀个最⼤解或最⼩解。

这样，两者在解这⼀⽅⾯还是有⼀些不同的。

之前回溯法讲了N后问题，这个问题也是对于这有多个解，但是今天讲的01背包问题是只有⼀个解的。

下⾯就讲讲分⽀限界法的基本思想。

分⽀限界法常以⼴度优先或以最⼩消耗（最⼤效益）优先的⽅式搜索问题的解空间树。

问题的解空间树是表⽰问题解空间的⼀颗有序树，常见的有⼦集树和排列树。

分⽀限界法和回溯法的区别还有⼀点，它们对于当前扩展结点所采⽤的扩展⽅式也是不相同的。

分⽀限界法中，对于每⼀个活结点只有⼀次机会成为扩展结点。

活结点⼀旦成为了扩展结点，就⼀次性产⽣其所有的⼦结点，⼦结点中，不符合要求的和⾮最优解的⼦结点将会被舍弃，剩下的⼦结点将加⼊到活结点表中。

再重复上⾯的过程，直到没有活结点表中没有结点，⾄此完成解决问题的⽬的。

分⽀限界法⼤致的思想就是上⾯的叙述，现在就可以发现，对于结点的扩展将会成为分⽀限界法的主要核⼼。

所以，分⽀限界法常见的有两种扩展结点的⽅式，1.队列式（FIFO）分⽀限界法，2.优先队列式分⽀限界法。

两种⽅法的区别就是对于活结点表中的取出结点的⽅式不同，第⼀种⽅法是先进先出的⽅式，第⼆种是按优先级取出结点的⽅式。

两中⽅法的区别下⾯也会提到。

在背包问题中还会提到⼀个⼦树上界的概念，其实就是回溯法中的剪枝函数，只不过，分⽀限界法⾥的剪枝函数改进了⼀些，剪枝函数同样也是分⽀限界法⾥⽐较重要的东西。

下⾯就讲⼀讲01背包问题的实现。

01背包问题和前⾯讲的背包问题的区别不⼤，就是01背包问题的物品不可以只放⼊部分，01背包问题的物品只能放⼊和不放⼊两个选择，这也是名字中01的原因。

其他的和背包问题相差不⼤，这⾥也不再累述。

算法的主体是⽐较容易想的，⾸先，将数据进⾏处理，这也是上⾯讲到的第⼆种取结点的⽅式（优先队列式）。

分⽀界限法0-1背包问题（优先队列式分⽀限界法）输⼊要求有多组数据。

每组数据包含2部分。

第⼀部分包含两个整数C （1 <= C <= 10000）和 n （1 <= n <= 10，分别表⽰背包的容量和物品的个数。

第⼆部分由n⾏数据，每⾏包括2个整数 wi（0< wi <= 100）和 vi（0 < vi <= 100），分别表⽰第i个物品的总量和价值输出要求对于每组输⼊数据，按出队次序输出每个结点的信息，包括所在层数，编号，背包中物品重量和价值。

每个结点的信息占⼀⾏，如果是叶⼦结点且其所代表的背包中物品价值⼤于当前最优值（初始为0），则输出当前最优值 bestv 和最优解bestx（另占⼀⾏）参见样例输出测试数据输⼊⽰例5 32 23 22 3输出⽰例1 1 0 02 2 2 23 5 2 24 10 4 5bestv=5, bestx=[ 1 0 1 ]4 11 2 23 4 5 42 3 0 0⼩贴⼠可采⽤如下的结构体存储结点：typedef struct{int no; // 结点在堆中的标号int sw; // 背包中物品的重量int sv; // 背包中物品的价值double prior; // 优先值 sv/sw}Node;#include<stdio.h>#include<math.h>#include<string.h>typedef struct {int no; // 结点标号int id; // 节点idint sw; // 背包中物品的重量int sv; // 背包中物品的价值double prior; // sv/sw}Node;int surplusValue(int *v,int n,int y) {int sum = 0;for(int i = y; i <= n; i++) {sum += v[i];}return sum;}void qsort(Node *que,int l,int r) {int len = r - l + 1;int flag;for(int i = 0; i < len; i ++) {flag = 0;for(int j = l; j < l + len - i; j++) {if(que[j].prior < que[j+1].prior) {Node t = que[j];que[j] = que[j+1];que[j+1] = t;flag = 1;}}//if(!flag ) return;}}void branchknap(int *w,int *v,int c,int n) {int bestv = 0;int f = 0;int r = 0;Node que[3000];memset(que,0,sizeof(que));int path[15];que[0].no = 1;que[0].id = que[0].sv = que[0].sw = que[0].prior = 0;while(f <= r) {Node node = que[f];printf("%d %d %d %d\n",node.id+1,node.no,node.sw,node.sv);if(node.no >= pow(2,n)) {if(node.sv > bestv) {bestv = node.sv;printf("bestv=%d, bestx=[",bestv);int temp = node.no;int i = 0;while(temp > 1) {if(temp % 2 == 0)path[i] = 1;elsepath[i] = 0;temp /= 2;i++ ;}i--;while(i >= 0) {while(i >= 0) {printf(" %d",path[i]);i--;}printf(" ]\n");}} else {if((node.sw + w[node.id + 1]) <= c && surplusValue(v,n,node.id+1) + node.sv > bestv) { r++;que[r].id = node.id + 1;que[r].no = node.no*2;int id = node.id + 1;que[r].sv = node.sv + v[id];que[r].sw = node.sw + w[id];que[r].prior = que[r].sv / (que[r].sw*1.0);}if(surplusValue(v,n,node.id+2) + node.sv > bestv) {r++;que[r].id = node.id + 1;que[r].no = node.no*2 + 1;que[r].sv = node.sv;que[r].sw = node.sw;que[r].prior = node.prior;}}f++;qsort(que,f,r);}}int main() {int c,n;int w[15],v[15];while(~scanf("%d %d",&c,&n)){for(int i = 1; i <= n; i++) {scanf("%d %d",&w[i],&v[i]);}branchknap(w,v,c,n);}return 0;}#include<stdio.h>#include<math.h>#include<string.h>typedef int bool;#define true 1#define false 0struct Node{int no; // ?áµ?±êo?int id; //jie dian idint sw; // ±3°ü?D·µá?int sv; // ±3°ü?D·µ?µdouble prior;};struct Node queuee[2000];int w[15],v[15];int bestv = 0,c,n;int path[15]; //lu jingint surplusValue(int y) {int sum = 0;for(int i = y; i <= n; i++)sum += v[i];return sum;}void qsort(int l,int r) {// printf("------\n");int len = r - l + 1;//printf("----%d %d %d-----\n",l,r,len);bool flag;for(int i = 0; i < len ; i++) {flag = false;for(int j = l; j <l+ len -i ;j++) {if(queuee[j].prior < queuee[j+1].prior) {struct Node temp = queuee[j];queuee[j] = queuee[j+1];queuee[j+1] = temp;flag = true;}//if(!flag) return;}}// printf("---排序嘻嘻---\n");//for(int i = l; i <= r;i++ )// printf("***%d : %.2lf\n",queuee[i].no,queuee[i].prior);// printf("\n------\n");}void branchknap() {bestv = 0;int f = 0;int r = 0;queuee[0].no = 1;queuee[0].id = 0;queuee[0].sv = 0;queuee[0].sw = 0;queuee[0].prior = 0;// printf("f: %d r: %d\n",f,r);while(f <= r) {struct Node node = queuee[f];printf("%d %d %d %d\n",node.id+1,node.no,node.sw,node.sv);if(node.no >= pow(2,n)) {if(node.sv > bestv) {bestv = node.sv;//TODOprintf("bestv=%d, bestx=[",bestv);int temp = node.no;int i = 0;while(temp > 1) {if(temp%2 == 0)path[i] = 1;elsepath[i] = 0;temp /= 2;i++;}i--;while(i >= 0) {while(i >= 0) {printf(" %d",path[i]);i--;}printf(" ]\n");}} else {if((node.sw + w[node.id+1]) <= c && surplusValue(node.id+1) + node.sv > bestv) { r++;//printf("%d\n",(node.sw + w[node.id+1]));queuee[r].id = node.id+1;queuee[r].no = node.no*2;int id = node.id+1;queuee[r].sv = node.sv + v[id];queuee[r].sw = node.sw + w[id];queuee[r].prior = queuee[r].sv/(queuee[r].sw*1.0);//printf("进队id： %d\n",queuee[r].no) ;//printf("%d %d %d\n",id,v[id], w[id]);}if(surplusValue(node.id+2) + node.sv > bestv) {r++;queuee[r].id = node.id+1;queuee[r].no = node.no*2 + 1;queuee[r].sv = node.sv ;queuee[r].sw = node.sw ;queuee[r].prior = node.prior;//printf("进队id： %d\n",queuee[r].no) ;}}f++;qsort(f,r);}}int main() {while(~scanf("%d %d",&c,&n)){memset(queuee,0,sizeof(queuee));for(int i = 1; i <= n; i++) {scanf("%d %d",&w[i],&v[i]);}branchknap();}return 0;}。

0/1 背包问题动态规划详解及C代码动态规划是用空间换时间的一种方法的抽象。

其关键是发现子问题和记录其结果。

然后利用这些结果减轻运算量。

比如01背包问题。

/* 一个旅行者有一个最多能用M公斤的背包，现在有N件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为P1,P2,...,Pn.若每种物品只有一件求旅行者能获得最大总价值。

输入格式：M,NW1,P1W2,P2......输出格式：X*/因为背包最大容量M未知。

所以，我们的程序要从1到M一个一个的试。

比如，开始任选N 件物品的一个。

看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。

怎么能保证总选择是最大价值呢？看下表。

测试数据：10,33,44,55,6c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。

加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。

总的最佳方案是5+4为9.这样.一排一排推下去。

最右下放的数据就是最大的价值了。

(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)从以上最大价值的构造过程中可以看出。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?下面是实际程序（在VC 6.0环境下通过）:#include<stdio.h>int c[10][100];/*对应每种情况的最大价值*/int knapsack(int m,int n){int i,j,w[10],p[10];printf("请输入每个物品的重量,价值：\n");for(i=1;i<=n;i++)scanf("%d,%d",&w[i],&p[i]);for(i=0;i<10;i++)for(j=0;j<100;j++)c[i][j]=0;/*初始化数组*/for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(w[i]<=j) /*如果当前物品的容量小于背包容量*/{if(p[i]+c[i-1][j-w[i]]>c[i-1][j])/*如果本物品的价值加上背包剩下的空间能放的物品的价值*//*大于上一次选择的最佳方案则更新c[i][j]*/c[i][j]=p[i]+c[i-1][j-w[i]];elsec[i][j]=c[i-1][j];}else c[i][j]=c[i-1][j];}return(c[n][m]);}int main(){int m,n;int i,j;printf("请输入背包的承重量,物品的总个数：\n");scanf("%d,%d",&m,&n);printf("旅行者背包能装的最大总价值为%d",knapsack(m,n)); printf("\n");return 0;}。

一、问题描绘0/1 背包问题 :现有 n 种物件，对1<=i<=n，已知第i 种物件的重量为正整数W i，价值为正整数V i，背包能蒙受的最大载重量为正整数W ，现要求找出这n 种物件的一个子集，使得子集中物品的总重量不超出W 且总价值尽量大。

（注意：这里对每种物件或许全取或许一点都不取，不一样意只取一部分）二、算法剖析依据问题描绘，能够将其转变为以下的拘束条件和目标函数：nw i x i W(1)i1x i{ 0,1}( 1i n)nmax v i x i (2)i1于是，问题就归纳为找寻一个知足拘束条件（ 1 ），并使目标函数式（ 2 ）达到最大的解向量 X(x1, x2 , x3 ,......, x n ) 。

第一说明一下0-1 背包问题拥有最优解。

假定 (x1, x2 , x3 ,......, x n ) 是所给的问题的一个最优解，则 (x2 , x3,......, x n ) 是下边问题的nw i x i W w1x1 maxn一个最优解：i 2v i x i。

假如不是的话，设( y2, y3 ,......, y n ) 是这x i{ 0,1}( 2i n)i 2n n n个问题的一个最优解，则v i y i v i x i，且 w1x1w i y i W 。

因此，i 2i 2i 2n n nv1x1v i y i v1 x1v i x i v i x i，这说明 (x1, y2 , y3 ,........, y n ) 是所给的0-1 背包问i 2i 2i 1题比 ( x1 , x2 , x3 ,........, x n ) 更优的解，进而与假定矛盾。

穷举法：用穷举法解决0-1 背包问题，需要考虑给定n 个物件会合的所有子集，找出所有可能的子集（总重量不超出背包重量的子集），计算每个子集的总重量，而后在他们中找到价值最大的子集。

因为程序过于简单，在这里就不再给出，用实例说明求解过程。

遗传算法求解0-1背包问题。

（步骤）#include "iostream.h"#include "iomanip.h"#include "stdlib.h"#include "math.h"#include "time.h"//定义问题的最大规模#define max 100//问题规模，即共有多少个包int packageNum;//每个包的重量int packageWeight[max];//每个包的价值int packageValue[max];//约束，背包的最大容量int limitWeight;//群体的规模int colonySize;//colonyState[i][k] 表示一个染色体//colonyState[1...colonySize][ 0|1 ] 表示一代群体int colonyState[max][2][max];// currAge 表示当前代的编号// (currAge+1)%2 表示下一代的编号int currAge = 0;//个体评价信息表typedef struct tagIndividualMsg{int index;int value;} IndividualMsg;IndividualMsg individualMsg[max];//////////////////////////////////////////////////////////// // 函数声明void printColonyState( int nextAge );//////////////////////////////////////////////////////////// //初始化群体void colonyInit(){int i , j;int w;for( i = 0 ; i < colonySize ; i++ ){//保证找到一个符合约束的染色体w = limitWeight + 1;while( w > limitWeight ){w = 0;for( j = 0 ; j < packageNum && w <= limitWeight ; j++ ){colonyState[i][currAge][j] = rand() % 2;w += packageWeight[j] * colonyState[i][currAge][j];}}}}//对个体进行评价int cmp( const void *a , const void *b ){IndividualMsg *x = (IndividualMsg *)a;IndividualMsg *y = (IndividualMsg *)b;return y->value - x->value;}void individualEstimate(){int i , j;for( i = 0 ; i < colonySize ; i++ ){individualMsg[i].index = i;individualMsg[i].value = 0;for( j = 0 ; j < packageNum ; j++ )individualMsg[i].value += packageValue[j] * colonyState[i][currAge][j]; }qsort( individualMsg , colonySize , sizeof(IndividualMsg) , cmp );}//终止循环的条件bool stopFlag(){//进行n 代进行后停止static int n = 50;if( n-- <= 0 )return true;elsereturn false;}//赌轮选择int gambleChoose(){int wheel[max] = { 0 };int i = colonySize - 1;int choose;wheel[i] = individualMsg[i].value;for( i-- ; i >= 0 ; i-- )wheel[i] = ( individualMsg[i].value + wheel[i+1] ) + colonySize * ( colonySize - i ); int seed = abs( wheel[0] - ( rand() % ( 2 * wheel[0] ) + 1 ) );choose = colonySize - 1;while( seed > wheel[choose] )choose--;// cout<<"----------------------------------------"<<endl;// cout<<"wheel :"<<endl;// for( i = 0 ; i < colonySize ; i++ )// cout<<setw(5)<<wheel[i];// cout<<endl;// cout<<"seed = "<<seed<<endl;// cout<<"choose "<<choose<<endl;return choose;}//交叉void across( int male , int female , int index ){int nextAge = (currAge+1)%2;int i , j , t;int acrossBit = rand() % (packageNum-1) + 1;for( j = 0 ; j < packageNum ; j++ ){colonyState[index][nextAge][j] =colonyState[individualMsg[male].index][currAge][j];colonyState[index+1][nextAge][j] =colonyState[individualMsg[female].index][currAge][j];}for( i = 0 ; i < acrossBit ; i++ ){t = colonyState[index][nextAge][i];colonyState[index][nextAge][i] = colonyState[index+1][nextAge][i];colonyState[index+1][nextAge][j] = t;}}//变异void aberrance( int index ){int seed , nextAge;nextAge = (currAge+1)%2;//只有1/3 的概率发生异变seed = rand() % ( packageNum * 3 );if( seed < packageNum )colonyState[index][nextAge][seed] = ( colonyState[index][nextAge][seed] + 1 ) % 2;}//处理死亡个体void dealDeath(){int i , j;int weight , w;int nextAge = (currAge+1)%2;for( i = 0 ; i < colonySize ; i++ ){weight = 0;for( j = 0 ; j < packageNum ; j++ )weight += packageWeight[j] * colonyState[i][nextAge][j];if( weight > limitWeight ){//随机生成新的个体w = limitWeight + 1;while( w > limitWeight ){w = 0;for( j = 0 ; j < packageNum && w <= limitWeight ; j++ ){colonyState[i][nextAge][j] = rand() % 2;w += packageWeight[j] * colonyState[i][nextAge][j];}}}}printColonyState( nextAge );}//最优个体保护void saveBest(){int i , j;int min , minp , value;int nextAge = ( currAge+1)%2;min = individualMsg[0].value;minp = -1;for( i = 0 ; i < colonySize ; i++ ){value = 0;for( j = 0 ; j < packageNum ; j++ )value += packageValue[j] * colonyState[i][nextAge][j]; if( value <= min ){min = value;minp = i;}}if( minp >= 0 ){for( j = 0 ; j < packageNum ; j++ ){colonyState[minp][nextAge][j] =colonyState[individualMsg[0].index][currAge][j];}}}//////////////////////////////////////////////////////////// void setProblem(){int i;packageNum = 5;int w[] = { 5 , 4 , 3 , 2 , 1 };int v[] = { 8 , 9 , 3 , 1 , 2 };for( i = 0 ; i < packageNum ; i++ ){packageWeight[i] = w[i];packageValue[i] = v[i];}limitWeight = 13;colonySize = 5;}void printProblem(){int i;cout<<"----------------------------------------"<<endl;cout<<"problem state:"<<endl;cout<<"packageNum = "<<packageNum<<endl;cout<<"limitWeight = "<<limitWeight<<endl;cout<<"Weight: ";for( i = 0 ; i < packageNum ; i++ )cout<<setw(3)<<packageWeight[i];cout<<endl;cout<<"Value: ";for( i = 0 ; i < packageNum ; i++ )cout<<setw(3)<<packageValue[i];cout<<endl;}void printColonyState( int k ){cout<<"----------------------------------------"<<endl;cout<<"colonyState-->";if( k == currAge )cout<<"currAge:"<<endl;elsecout<<"next age:"<<endl;int i , j;for( i = 0 ; i < colonySize ; i++ ){for( j = 0 ; j < packageNum ; j++ )cout<<setw(2)<<colonyState[i][k][j];cout<<endl;}}void printIndividualMsg(){int i;cout<<"----------------------------------------"<<endl;cout<<"Individual Msg:"<<endl;for( i = 0 ; i < colonySize ; i++ ){cout<<individualMsg[i].index<<"\t"<<individualMsg[i].value<<endl; }}////////////////////////////////////////////////////////////void main(){srand( (unsigned int)time(NULL) );setProblem();printProblem();//初始群体colonyInit();printColonyState( currAge );while( !stopFlag() ){//评价当前群体individualEstimate();//生成下一代for( int i = 0 ; i < colonySize ; i += 2 ){int male = gambleChoose();int female = gambleChoose();across( male , female , i );aberrance( i );aberrance( i + 1 );}//处理死亡个体dealDeath();//最优个体保护saveBest();//现在的下一代变成下一轮的当前代currAge = ( currAge + 1 ) % 2;//printColonyState( currAge );}//输出问题解individualEstimate();cout<<"近似解:"<<endl;int j , w = 0;cout<<setw(10)<<"Value:";for( j = 0 ; j < packageNum ; j++ )cout<<setw(5)<<packageValue[j];cout<<endl;cout<<setw(10)<<"Weight:";for( j = 0 ; j < packageNum ; j++ ){w += packageWeight[j] * colonyState[individualMsg[0].index][currAge][j]; cout<<setw(5)<<packageWeight[j];}cout<<endl;cout<<setw(10)<<"Choose:";for( j = 0 ; j < packageNum ; j++ )cout<<setw(5)<<colonyState[individualMsg[0].index][currAge][j];cout<<endl;cout<<"limitWeight: "<<limitWeight<<endl;cout<<"总重量: "<<w<<endl;cout<<"总价值: "<<individualMsg[0].value<<endl; }////////////////////////////////////////////////////////////。

0-1背包问题(回溯法)实验报告姓名：学号：指导老师：一．算法设计名称：0-1背包问题（回溯法）二.实验内容问题描述:给定n 种物品和一背包。

物品i 的重量是w i ，其价值为v i ，背包的容量为C 。

问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i 只有两种选择，即装入背包或不装入背包。

不能将物品装入背包多次，也不能只装入部分的物品。

三.实验目的1.运用回溯思想，设计解决上述问题的算法，找出最大背包价值的装法。

2.掌握回溯法的应用四．算法设计：问题求解思路1.由0-1背包问题的最优子结构性质，建立计算m[i][j]的递归式如下：i i i w j w j j i m i v w j i m j i m j i m <≤≥⎩⎨⎧-+---=0],1[]}[],1[],,1[max{),(2.查找装入背包物品的回溯函数：从0-1二叉树的根开始搜索：若是叶子节点，则判断此时的价值是否比当前最优的价值大，否则将之替换，并获得最优解向量且返回；若不是叶子节点，则向左右子树搜索，先改变当前的数据状态，递归的调用自己，然后恢复数据状态表示回溯。

3.边界函数bound主要是当还未搜索到叶子节点时，提前判断其子树是否存可能存在更优的解空间，否则进行回溯，即裁剪掉子树的解空间。

关键数据结构及函数模块：（Backtrack.h ）#ifndef __BACKTRACK_H__#define __BACKTRACK_H__class BP_01_P{public:∑=ni i i x v 1max ⎪⎩⎪⎨⎧≤≤∈≤∑=n i x C x w i n i i i 1},1,0{1BP_01_P(int w,int n):m_Sum_weitht(0),m_Number(0) {m_Sum_weitht=w;m_Number=n;bestHav=0;bestVal=0;curVal=0;curHav=0;m_hav=new int[n];m_val=new int[n];temop=new int[n];option=new int[n];}~BP_01_P(){delete []m_hav;delete []m_val;delete []temop;delete []option;}void traceBack(int n);int bound(int n);void printBestSoulation();int *m_hav;//每个物品的重量int *m_val;//每个物品的价值int *temop;//01临时解int *option;//01最终解int bestHav;//最优价值时的最大重量int bestVal;//最优的价值int curVal;//当前的价值int curHav;//当前的重量private:int m_Sum_weitht;//背包的总容量int m_Number;//物品的种类};#endif __BACKTRACK_H__五：主要的算法代码实现：（Backtrack.cpp）边界函数：bound( )int BP_01_P::bound(int n){int hav_left=m_Sum_weitht-curHav;int bo=curVal;while(n<m_Number && m_hav[n]<=hav_left){hav_left-=m_hav[n];bo+=m_val[n];n++;}if(n<m_Number){bo+=m_val[n]*hav_left/m_hav[n];//bo+=hav_left;}return bo;}回溯递归函数：traceBack( )void BP_01_P::traceBack(int n){if(n>=m_Number){if(curVal>=bestVal){bestVal=curVal;for(int i=0;i<n;i++){option[i]=temop[i];}return ;}}if(curHav+m_hav[n]<=m_Sum_weitht)//向左子树搜索 {curHav=curHav+m_hav[n];curVal=curVal+m_val[n];temop[n]=1;//标记要选择这个物品traceBack(n+1);curHav=curHav-m_hav[n];curVal=curVal-m_val[n];}if(bound(n+1)>bestVal)//向右子树搜索{temop[n]=0;//标记要丢弃这个物品traceBack(n+1);}}主控函数：(main.cpp)#include <iostream>#include "Backtrack.h"using namespace std;int main(){int number,weigth;cout<<"包的总容量:";cin>>weigth;cout<<"物品的种类:";cin>>number;BP_01_P *ptr=new BP_01_P(weigth,number);cout<<"各种物品的重量:"<<endl;for(int i=0;i<number;i++)cin>>ptr->m_hav[i];cout<<"各种物品的价值:"<<endl;for(i=0;i<number;i++)cin>>ptr->m_val[i];ptr->traceBack(0);ptr->printBestSoulation();cout<<"总重量:"<<ptr->bestHav<<"\t总价值:"<<ptr->bestVal<<endl;return 0;}六：算法分析采用回溯法解决0-1背包问题，明显比动态规划法更优良。

0-1背包问题的递归方法0-1背包问题是一个经典的动态规划问题，可以使用递归方法求解。

定义一个函数`knapsack(weights, values, capacity, n)`，其中`weights`和`values`分别代表物品的重量和价值，`capacity`代表背包的容量，`n`代表当前考虑的物品个数。

递归的思路是对于每个物品，有两种选择：放入背包中或者不放入背包中。

1. 如果第`n`个物品的重量大于背包的容量`capacity`，则不放入背包中，返回`0`；2. 否则，有两种选择：- 选择放入第`n`个物品，则总价值为第`n`个物品的价值加上考虑前`n-1`个物品，背包容量减去第`n`个物品重量的最优解； - 不放入第`n`个物品，则总价值为考虑前`n-1`个物品，背包容量不变的最优解。

代码如下所示：```pythondef knapsack(weights, values, capacity, n):if n == 0 or capacity == 0:return 0if weights[n-1] > capacity:return knapsack(weights, values, capacity, n-1)else:return max(values[n-1] + knapsack(weights, values, capacity-weights[n-1], n-1),knapsack(weights, values, capacity, n-1))```可以通过调用`knapsack`函数来求解0-1背包问题，如下所示：```pythonweights = [2, 3, 4, 5]values = [3, 4, 5, 6]capacity = 5n = len(weights)result = knapsack(weights, values, capacity, n)print(result)```以上代码会输出最优解的总价值。

分支限界法——01背包问题12软工028 胡梦颖一、问题描述0-1背包问题：给定n种物品和一个背包。

物品i的重量是Wi，其价值为Vi，背包的容量为C。

应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。

不能将物品i装入背包多次，也不能只装入部分的物品i。

二、问题分析分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。

一般情况下，分支限界法与回溯法的求解目标不同。

回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。

回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。

分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。

为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

这种方式称为分支限界法。

人们已经用分支限界法解决了大量离散最优化的问题。

三．源代码#include <stdio.h>#include<malloc.h>#define MaxSize 100 //结点数的最大值typedef struct QNode{float weight;float value;int ceng;struct QNode *parent;bool leftChild;}QNode,*qnode;typedef struct{qnode Q[MaxSize];int front,rear;}SqQueue; //存放结点的队列SqQueue sq;float bestv=0; //最优解int n=0; //实际物品数float w[MaxSize]; //物品的重量float v[MaxSize]; //物品的价值int bestx[MaxSize]; // 存放最优解qnode bestE;void InitQueue(SqQueue &sq ) //队列初始化{sq.front=1;sq.rear=1;}bool QueueEmpty(SqQueue sq) //队列是否为空{if(sq.front==sq.rear)return true;elsereturn false;}void EnQueue(SqQueue &sq,qnode b) //入队{if(sq.front==(sq.rear+1)%MaxSize){printf("队列已满!");return;}sq.Q[sq.rear]=b;sq.rear=(sq.rear+1)%MaxSize;} qnode DeQueue(SqQueue &sq) //出队{qnode e;if(sq.front==sq.rear){printf("队列已空!");return 0;}e=sq.Q[sq.front];sq.front=(sq.front+1)%MaxSize;return e;}void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild) {qnode b;if (i==n) //可行叶子结点{ if (vt==bestv){ bestE=parent;bestx[n]=(leftchild)?1:0;}return;}b=(qnode)malloc(sizeof(QNode)); //非叶子结点b->weight=wt;b->value=vt;b->ceng=i;b->parent=parent;b->leftChild=leftchild;EnQueue(sq,b);}void maxLoading(float w[],float v[],int c){float wt=0;float vt=0;int i=1; //当前的扩展结点所在的层float ew=0; //扩展节点所相应的当前载重量float ev=0; //扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t); //空标志进队列while (!QueueEmpty(sq)){wt=ew+w[i];vt=ev+v[i];if (wt <= c){if(vt>bestv)bestv=vt;EnQueue1(wt,vt,i,e,true); // 左儿子结点进队列} EnQueue1(ew,ev,i,e,false); //右儿子总是可行；e=DeQueue(sq); // 取下一扩展结点if (e == NULL){if (QueueEmpty(sq))break;EnQueue(sq,NULL); // 同层结点尾部标志e=DeQueue(sq); // 取下一扩展结点i++;}ew=e->weight; //更新当前扩展结点的值ev=e->value;}printf("最优取法为：\n");for( int j=n-1;j>0;j--) //构造最优解{bestx[j]=(bestE->leftChild?1:0);bestE=bestE->parent;}for(int k=1;k<=n;k++){if(bestx[k]==1)printf("物品%d:重量：%.1f，价值：%.1f\n",k,w[k],v[k]);}printf("最大价值为：%.1f\n",bestv);}void main(){int c;float ewv[MaxSize];printf("请输入背包的最大容量v:");scanf("%d",&c);printf("请输入物品总数n:");scanf("%d",&n);printf("请输入物品的重量和单位重量价值:\n");for(int i=1;i<=n;i++){printf("第%d件物品:",i);scanf("%f%f",&w[i],&ewv[i]);v[i]=w[i]*ewv[i];}maxLoading(w,v,c);}五．实验结果。

旅⾏售货员问题（分⽀限界法）⼀、实验内容运⽤分⽀限界法解决0-1背包问题（或者旅⾏售货员问题、或者装载问题、或者批处理作业调度）使⽤优先队列式分⽀限界法来求解旅⾏售货员问题⼆、所⽤算法基本思想及复杂度分析1.算法基本思想分⽀限界法常以⼴度优先或以最⼩耗费有限的⽅式搜索问题的解空间树。

问题的解空间树是表⽰问题解空间的⼀棵有序树，常见的有⼦集树和排列树。

在搜索问题的解空间树时，分⽀限界法和回溯法的主要区别在于它们对当前扩展节点所采⽤的扩展⽅式不同。

在分⽀限界法中，每⼀个活结点只有⼀次机会成为扩展节点。

活结点⼀旦成为扩展节点，就⼀次性产⽣其所有⼉⼦节点。

在这些⼉⼦节点中，导致不可⾏解或导致⾮最优解的⼉⼦节点被舍弃，其余⼉⼦节点被加⼊活结点表中。

此后，从活结点表中取下⼀节点为当前扩展节点。

并重复上述节点扩展过程。

这个过程移⾄持续到找到所需的解或活结点表为空为⽌。

从活结点表中选择下⼀扩展节点的不同⽅式导致不同的分⽀限界法。

最常见的有以下两种⽅式：（1）队列式分⽀限界法队列式分⽀限界法将活结点表组织成⼀个队列，并按队列的先进先出原则选取下⼀个节点为当前扩展节点。

（2）优先队列式分⽀限界法优先队列式的分⽀限界法将活结点表组织成⼀个优先队列，并按优先队列中规定的节点优先级选取优先级最⾼的下⼀个节点成为当前扩展节点。

2.问题分析及算法设计问题分析：（1）解旅⾏售货员问题的优先队列式分⽀限界法⽤优先队列存储活结点表。

（2）活结点m在优先队列中的优先级定义为：活结点m对应的⼦树费⽤下界lcost。

（3）lcost=cc+rcost，其中，cc为当前结点费⽤，rcost为当前顶点最⼩出边费⽤加上剩余所有顶点的最⼩出边费⽤和。

（4）优先队列中优先级最⼤的活结点成为下⼀个扩展结点。

（5）排列树中叶结点所相应的载重量与其优先级（下界值）相同，即：叶结点所相应的回路的费⽤(bestc)等于⼦树费⽤下界lcost的值。

算法设计：（1）要找最⼩费⽤旅⾏售货员回路，选⽤最⼩堆表⽰活结点优先队列。

实验报告课程计算机算法设计与分析实验名称最大子段和、0-1背包问题学号姓名实验日期：实验二最大子段和、0-1背包问题一．实验目的（1）学习最大子段和问题的简单算法，掌握原理，运用C++编程实现。

（2）学习0-1背包问题的简单算法，掌握原理，运用C++编程实现。

二．实验内容（1）设计最大子段和问题的算法,上机编程实现。

（2）设计0-1背包问题的算法，上机编程实现。

三．实验代码1 .分治法实现最大子段和程序如下：#include<iostream.h>int MaxSum(int a[],int left,int right){int sum=0;if (left==right){if (a[left]>0)sum=a[left];elsesum=0;}else{int center=(left+right)/2;int leftsum=MaxSum(a,left,center);int rightsum=MaxSum(a,center+1,right);int s1=0;int lefts=0;for(int i=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}int s2=0;int rights=0;for(int j=center+1;j<=right;j++){rights+=a[j];if(rights>s2)s2=rights;}sum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;}return sum;}void main(){int n,a[100],m,maxsum;cout<<"分治法求解"<<endl;cout<<"请输入待求的元素数目"<<endl;cin>>n;cout<<"请输入各元素"<<endl;for(m=1;m<=n;m++)cin>>a[m];maxsum=MaxSum(a,1,n);cout<<"当前序列最大子段和为："<<maxsum<<endl; }（2）0-1背包问题程序如下：#include<iostream>#include<cstdio>#include<conio.h>#include<iomanip>using namespace std;template<class ty>class Knap{ public:friend void Init();friend void Knapsack();friend void Backtrack(int i);friend float Bound(int i);bool operator<(Knap<ty> a)const{ if(fl<a.fl)return true;elsereturn false; }private:ty w; //重量ty v; //价值float fl; //单位重量的价值v/wint kk; //记录第几个物品int flag; //记录是否放入包中};template<class ty>void Sort(Knap<ty> *li,int n){ int i,j,k;Knap<ty> minl;for(i=1;i<n;i++){ minl=li[0];k=0;for(j=1;j<=n-i;j++){ if(minl<li[j]){ minl=li[j];swap(li[j],li[k]);k=j; } } } }namespace jie //命名空间{ int c=0,n=0;int *x=NULL;Knap<int> *bag=NULL;int cp=0,cw=0; int bestp=0; }using namespace jie;void Init(){ int i=0;cout<<endl;cout<<"请输入物品数量n = ";cin>>n;cout<<endl;cout<<"请输入背包容量C = ";cin>>c;cout<<endl;bag=new Knap<int> [n];x=new int[n];cout<<"请依次输入"<<n<<"个物品的重量W:"<<endl; for(i=0;i<n;i++)cin>>bag[i].w;cout<<endl;cout<<"请依次输入"<<n<<"个物品的价值P:"<<endl; for(i=0;i<n;i++)cin>>bag[i].v;for(i=0;i<n;i++){ bag[i].flag=0;bag[i].kk=i;bag[i].fl=1.0*bag[i].v/bag[i].w;}}void Backtrack(int i) { if(i>=n) //到达叶节点{ bestp=cp; //更新最优价值return; }if(cw+bag[i].w<=c) //进入左子树{ bag[i].flag=1;cw+=bag[i].w;cp+=bag[i].v;Backtrack(i+1);cw-=bag[i].w;cp-=bag[i].v; }if(Bound(i+1)>bestp)//进入右子树{ bag[i].flag=0;Backtrack(i+1); } } //计算当前节点处的上界float Bound(int i){ int cleft = c-cw; //剩余容量float b = cp;while (i<n&&bag[i].w<=cleft){ //以物品单位重量价值递减序装入cleft-=bag[i].w;b+=bag[i].v;i++; } //装满背包if (i<n) b+=1.0*bag[i].v/bag[i].w * cleft;return b; }void Knapsack() //计算最优解和变量值{ int L(0); //用L累计价值，初始价值设置为0for(int k=0;k<n;k++){ x[bag[k].kk]=bag[k].flag; //x=0表示未放入背包，x=1表示放入背包L+=bag[k].flag*bag[k].v; //价值累加}cout<<endl;cout<<"当前最优价值为:"<<L<<endl;cout<<"变量值x = ";for(int i=1;i<=n;i++){ cout<<x[i-1]; }delete []bag;bag=NULL;delete []x;x=NULL;cout<<endl;getch(); }int main(){ cout<<endl;cout<<"|**********回溯法解0-1背包问题**********|"<<endl;Init();Backtrack(0);Knapsack();return 0;}四．实验结果（1）分治法最大子段和问题运行结果如下：（2）0-1背包问题运行结果如下：五．总结与思考。