回溯法、分支限界法解0-1背包问题(计算机算法设计与分析实验报告)

回溯法解决0-1背包问题问题描述： 有n件物品和⼀个容量为c的背包。

第i件物品的价值是v[i]，重量是w[i]。

求解将哪些物品装⼊背包可使价值总和最⼤。

所谓01背包，表⽰每⼀个物品只有⼀个，要么装⼊，要么不装⼊。

回溯法： 01背包属于找最优解问题，⽤回溯法需要构造解的⼦集树。

在搜索状态空间树时，只要左⼦节点是可⼀个可⾏结点，搜索就进⼊其左⼦树。

对于右⼦树时，先计算上界函数，以判断是否将其减去，剪枝啦啦！上界函数bound():当前价值cw+剩余容量可容纳的最⼤价值<=当前最优价值bestp。

为了更好地计算和运⽤上界函数剪枝，选择先将物品按照其单位重量价值从⼤到⼩排序，此后就按照顺序考虑各个物品。

#include <stdio.h>#include <conio.h>int n;//物品数量double c;//背包容量double v[100];//各个物品的价值double w[100];//各个物品的重量double cw = 0.0;//当前背包重量double cp = 0.0;//当前背包中物品价值double bestp = 0.0;//当前最优价值double perp[100];//单位物品价值排序后int order[100];//物品编号int put[100];//设置是否装⼊//按单位价值排序void knapsack(){int i,j;int temporder = 0;double temp = 0.0;for(i=1;i<=n;i++)perp[i]=v[i]/w[i];for(i=1;i<=n-1;i++){for(j=i+1;j<=n;j++)if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]{temp = perp[i];perp[i]=perp[i];perp[j]=temp;temporder=order[i];order[i]=order[j];order[j]=temporder;temp = v[i];v[i]=v[j];v[j]=temp;temp=w[i];w[i]=w[j];w[j]=temp;}}}//回溯函数void backtrack(int i){double bound(int i);if(i>n){bestp = cp;return;}if(cw+w[i]<=c){cw+=w[i];cp+=v[i];put[i]=1;backtrack(i+1);cw-=w[i];cp-=v[i];}if(bound(i+1)>bestp)//符合条件搜索右⼦数backtrack(i+1);}//计算上界函数double bound(int i){double leftw= c-cw;double b = cp;while(i<=n&&w[i]<=leftw){leftw-=w[i];b+=v[i];i++;}if(i<=n)b+=v[i]/w[i]*leftw;return b;}int main(){int i;printf("请输⼊物品的数量和容量：");scanf("%d %lf",&n,&c);printf("请输⼊物品的重量和价值：");for(i=1;i<=n;i++){printf("第%d个物品的重量：",i);scanf("%lf",&w[i]);printf("价值是：");scanf("%lf",&v[i]);order[i]=i;}knapsack();backtrack(1);printf("最有价值为：%lf\n",bestp);printf("需要装⼊的物品编号是：");for(i=1;i<=n;i++){if(put[i]==1)printf("%d ",order[i]);}return 0;}时间复杂度分析： 上界函数bound()需要O(n)时间，在最坏的情况下有O(2^n)个右⼦结点需要计算上界，回溯算法backtrack需要的计算时间为O(n2^n)。

一、实验目的1. 理解回溯法的基本原理和适用场景。

2. 掌握回溯法在解决实际问题中的应用。

3. 通过实验，提高编程能力和算法设计能力。

二、实验背景回溯法是一种在计算机科学中广泛应用的算法设计方法。

它通过尝试所有可能的解，在满足约束条件的前提下，逐步排除不满足条件的解，从而找到问题的最优解。

回溯法适用于解决组合优化问题，如0-1背包问题、迷宫问题、图的着色问题等。

三、实验内容本次实验以0-1背包问题为例，采用回溯法进行求解。

1. 实验环境：Windows操作系统，Python 3.7以上版本。

2. 实验工具：Python编程语言。

3. 实验步骤：（1）定义背包容量和物品重量、价值列表。

（2）定义回溯法函数，用于遍历所有可能的解。

（3）在回溯法函数中，判断当前解是否满足背包容量约束。

（4）若满足约束，则计算当前解的价值，并更新最大价值。

（5）若不满足约束，则回溯至前一步，尝试下一个解。

（6）输出最优解及其价值。

四、实验结果与分析1. 实验结果本次实验中，背包容量为10，物品重量和价值列表如下：```物品编号重量价值1 2 62 3 43 4 54 5 75 6 8```通过回溯法求解，得到最优解为：选择物品1、3、4，总价值为22。

2. 实验分析（1）回溯法能够有效地解决0-1背包问题，通过遍历所有可能的解，找到最优解。

（2）实验结果表明，回溯法在解决组合优化问题时具有较高的效率。

（3）在实验过程中，需要合理设计回溯法函数，以提高算法的效率。

五、实验总结通过本次实验，我们了解了回溯法的基本原理和适用场景，掌握了回溯法在解决实际问题中的应用。

在实验过程中，我们提高了编程能力和算法设计能力，为今后解决类似问题奠定了基础。

在今后的学习和工作中，我们将继续深入研究回溯法及其应用，以期为解决实际问题提供更多思路和方法。

算法设计与分析实验报告—0/1背包问题-【问题描述】给定n 种物品和一个背包。

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

问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？【问题分析】0/1背包问题的可形式化描述为：给定C>0, i w >0, i v >0,1i n ≤≤，要求找出n 元0/1向量{}12(,,...,),0,1,1n i x x x x i n ∈≤≤，使得n1i i i w x c =≤∑，而且n1i ii v x=∑达到最大。

因此0/1背包问题是一个特殊的整数规划问题。

0n k w ≤≤1max ni i i v x =∑n1i ii w xc =≤∑{}0,1,1i x i n ∈≤≤【算法设计】设0/1背包问题的最优值为m( i, j )，即背包容量是j ，可选择物品为i,i+1,…,n 时0/1背包问题的最优值。

由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下：max{m( i+1, j ), m( i+1, j-i w )+i v } i j w ≥m( i, j )=m(i+1,j)n v n j w >m(n,j)=0 0n k w ≤≤【算法实现】#include <iostream.h> #include<string.h> #include<iomanip.h>int min(int w, int c) {int temp; if (w < c) temp = w;elsetemp = c;return temp;}Int max(int w, int c) {int temp; if (w > c) temp = w;elsetemp = c;return temp;}void knapsack(int v[], int w[], int** m, int c, int n) //求最优值 {int jmax = min(w[n]-1, c);for (int j = 0; j <= jmax; j++)m[n][j] = 0;for (int jj = w[n]; jj <= c; jj++)m[n][jj] = v[n];for(int i = n-1; i > 1; i--)//递归部分{jmax = min(w[i]-1, c);for(int j = 0; j <= jmax; j++)m[i][j] = m[i+1][j];for(int jj = w[i]; jj <= c; jj++)m[i][jj] = max(m[i+1][jj], m[i+1][jj-w[i]]+v[i]);}m[1][c] = m[2][c];if(c >= w[1])m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);cout << endl << "最优值：" << m[1][c] << endl;cout<<endl;cout<< "&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&" << endl;}int traceback(int x[], int w[], int** m, int c, int n) //回代，求最优解{out << endl << "得到的一组最优解如下: " << endl;for(int i = 1; i < n; i++){if(m[i][c] == m[i+1][c]) x[i] = 0;else{x[i] = 1;c -= w[i];}}x[n] = (m[n][c]) ? 1:0;for(int y = 1; y <= n; y++)cout << x[y] << "\t";cout << endl;return x[n];}void main(){int n, c;int **m;cout << "&&&&&&&&&&&&&&&&&&&&&欢迎使用0-1背包问题程序&&&&&&&&&&&&&&&&&&&" << endl;cout << "请输入物品个数: ";cin >> n ;cout << endl << "请输入背包的承重：";cin >> c;int *v = new int[n+1];cout << endl << "请输入每个物品的价值 (v[i]): " << endl;for(int i = 1; i <= n; i++)cin >> v[i];int *w = new int[n+1];cout << endl << "请输入每个物品的重量 (w[i]): " << endl;for(int j = 1; j <= n; j++)cin >> w[j];int *x = new int[n+1];m = new int* [n+1]; //动态的分配二维数组for(int p = 0; p < n+1; p++)m[p] = new int[c+1];knapsack (v, w, m, c, n);traceback(x, w, m, c, n);}【运行结果】。

算法分析与设计实验报告第7 次实验}1、测试自己输入的小规模数据2、测试随机生成1003、随机生成1000数据4、随机生成1000数据附录：完整代码#include <iostream>#include<time.h>#include<algorithm>#include<fstream>using namespace std;ifstream in("input.txt");ofstream out("output.txt");typedef int Typew;typedef int Typep;//物品类class Object{friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); public:int operator <= (Object a) const{return (d >= a.d);}private:int ID; //物品编号float d; //单位重量价值};//树结点类class bbnode{friend class Knap;friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); private:bbnode *parent; //指向父节点的指针int LChild;};//堆结点类class HeapNode{friend class Knap;friend class MaxHeap;public:operator Typep()const{return uprofit;};private:Typep uprofit, //结点的价值上界profit; //结点所相应的价值Typew weight; //结点所相应的重量int level; //活结点在子集树中所处的层序号bbnode *elemPtr; //指向该活结点在子集树中相应结点的指针};//最大堆类class MaxHeap{public:MaxHeap(int maxElem){HeapElem = new HeapNode* [maxElem+1]; //下标为0的保留capacity = maxElem;size = 0;}void InsertMax(HeapNode *newNode);HeapNode DeleteMax(HeapNode* &N);private:int capacity;int size;HeapNode **HeapElem;};//0-1背包问题的主类class Knap{friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); public:Typep MaxKnapsack();private:MaxHeap *H;Typep Bound(int i);void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level);bbnode *E; //指向扩展结点的指针Typew c; //背包容量int n; //物品总数Typew *w; //物品重量数组（以单位重量价值降序）Typep *p; //物品价值数组（以单位重量价值降序）Typew cw; //当前装包重量Typep cp; //当前装包价值int *bestx; //最优解};void MaxHeap::InsertMax(HeapNode *newNode){int i = 1;for (i = ++size; i/2 > 0 && HeapElem[i/2]->uprofit < newNode->uprofit; i /= 2){HeapElem[i] = HeapElem[i/2];}HeapElem[i] = newNode;}HeapNode MaxHeap::DeleteMax(HeapNode *&N){if(size >0 ){N = HeapElem[1];int i = 1;while(i < size){if(((i*2 +1) <= size) && HeapElem[i*2]->uprofit > HeapElem[i*2 +1]->uprofit){HeapElem[i] = HeapElem[i*2];i = i*2;}else{if(i*2 <= size){HeapElem[i] = HeapElem[i*2];i = i*2;}elsebreak;}}if(i < size)HeapElem[i] = HeapElem[size];}size--;return *N;}Typep Knap::MaxKnapsack(){H = new MaxHeap(10000);bestx = new int [n+1];int i = 1;E = 0;cw = 0;cp = 0;Typep bestp = 0;Typep up = Bound(1);while (i != n+1){Typew wt = cw + w[i];if(wt <= c) {if(cp + p[i] > bestp)bestp = cp + p[i];AddLiveNode(up, cp + p[i], cw + w[i], 1, i);}up = Bound(i + 1);if(up >= bestp)AddLiveNode(up, cp, cw, 0, i);HeapNode* N;H->DeleteMax(N);E = N->elemPtr;cw = N->weight;cp = N->profit;up = N->uprofit;i = N->level + 1;}for (int i = n; i > 0; i--){bestx[i] = E->LChild;E = E->parent;}return cp;}Typep Knap::Bound(int i){Typew cleft = c - cw;Typep b = cp;while (i<=n && w[i] <= cleft){cleft -= w[i];b += p[i];i++;}if(i<=n) b += p[i]/w[i] * cleft;return b;}void Knap::AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level) {bbnode *b=new bbnode;b->parent=E;b->LChild=ch;HeapNode *N = new HeapNode;N->uprofit=up;N->profit=cp;N->weight=cw;N->level=level;N->elemPtr=b;H->InsertMax(N);}//Knapsack返回最大价值，最优值保存在bestxTypep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx){Typew W = 0;Typep P = 0;Object *Q = new Object[n];for(int i =1; i<=n; i++){Q[i-1].ID = i;Q[i-1].d = 1.0*p[i]/w[i];P += p[i];W += w[i];}if (W <= c){for(int i =1; i<=n; i++){bestx[i] = p[i];}return P;}for(int i = 1; i<n; i++)for(int j = 1; j<= n-i; j++){if(Q[j-1].d < Q[j].d){Object temp = Q[j-1];Q[j-1] = Q[j];Q[j] = temp;}}Knap K;K.p = new Typep [n+1];K.w = new Typew [n+1];for(int i = 1; i<=n; i++){K.p[i] = p[Q[i-1].ID];K.w[i] = w[Q[i-1].ID];}K.cp = 0;K.cw = 0;K.c = c;K.n = n;Typep bestp = K.MaxKnapsack();for(int i = 1; i<=n; i++){bestx[Q[i-1].ID] = K.bestx[i];}delete [] Q;delete [] K.w;delete [] K.p;delete [] K.bestx;delete [] K.H;return bestp;}int main(){cout<<"请在input.txt文件中输入物品数量、背包容量"<<endl;int N ;in>>N;Typew c; //背包容量in>>c;int bestx[N+1]; //最优解int bestp; //最优值Typep p[N+1];//物品价值Typew w[N+1];//物品重量cout<<"在input.txt文件中读取的物品总数N = "<< N<<",背包容量C = "<< c<<endl; cout<<"请选择生成数据的规模大小：200请输入1,2000请输入2，20000请输入3"<<endl; int x;cin>>x;if(x==1){ofstream in1("input1.txt");srand(time(NULL));int n=200;int *a=new int[n];for(int i=0;i<n;i++){a[i]=rand()%91;in1<<a[i]<<" ";}cout<<"随机数已请生成到input1文件中，请将数据添加到input.txt文件中"<<endl; }else if(x==2){ofstream in1("input1.txt");srand(time(NULL));int n=2000;int *a=new int[n];for(int i=0;i<n;i++){a[i]=rand()%91;in1<<a[i]<<" ";}cout<<"随机数已请生成到input1文件中，请将数据添加到input.txt文件中"<<endl; }else if(x==3){ofstream in1("input1.txt");srand(time(NULL));int n=20000;int *a=new int[n];for(int i=0;i<n;i++){a[i]=rand()%91;in1<<a[i]<<" ";}cout<<"随机数已请生成到input1文件中，请将数据添加到input.txt文件中"<<endl;}cout<<"添加完毕后请输入1"<<endl;int m;cin>>m;clock_t start,finish;start=clock();for (int i = 1; i <= N; i++){in>>w[i];}for (int i = 1; i <= N; i++){in>>p[i];}cout<<"已在input文件中读取物品重量和价值。

一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解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的原因。

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

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

[精品]实验报告回溯法01背包实验目的：掌握回溯法的基本思想和流程，了解01背包问题，并用回溯法求解。

实验原理：回溯法是一种利用搜素树策略求解问题的思想，在问题的求解过程中，采用试错的方法，先从问题的一个可能的解答开始搜素，如果发现在这个答案上已经出现了错误，就返回到上一个状态，尝试其他可能的解答。

回溯法可以看作是深度优先搜素算法的一种特殊情况，它在搜素过程中判断是否满足约束条件，如果不满足，则进行回溯。

01背包问题是指在给定的一组物品中，选取若干个物品放入一个容量为V的背包中，使得背包能够容纳的物品总价值最大。

其中，每个物品只有一个，可以选择放或不放。

实验过程：实验采用C++语言编写程序，首先自定义一个物品结构体，包括物品的编号、重量和价值。

由于只有一组物品，所以可以定义一个全局数组存储物品信息。

然后，定义一个函数backtrack(int i, int cw, int cv)，其中i表示当前处理到的物品编号，cw表示当前物品已经放入背包的重量，cv表示当前物品已经放入背包的价值。

函数中，先判断当前物品是否可以放入背包中，如果可以，则更新背包重量和价值，并继续对下一个物品进行搜素；如果不可以，则进行回溯。

回溯时，需要将当前物品从背包中取出，并将已经放入背包的重量和价值还原到回溯前的状态，然后尝试选择其他方案。

程序中，需要定义一个全局变量Maxv存储当前已经求得的最大价值，每次更新最大价值时，也需要将最优解存储下来。

实验结果：经过运行程序，可以得到01背包问题的最优解为45，选取的物品编号为1、3、5。

回溯法是一种基于搜素树策略的算法，适用于求解复杂问题。

在应用回溯法求解问题时，需要注意约束条件的判断和回溯操作的正确性，以及最优解的存储方法。

实验报告课程名称：算法设计与分析实验名称：解0-1背包问题任课教师：王锦彪专业：计算机应用技术班级: 2011 学号： ****** 姓名：严焱心完成日期： 2011年11月一、实验目的：掌握动态规划、贪心算法、回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对上述方法的理解。

二、实验内容及要求：1． 要求分别用动态规划、贪心算法、回溯法和分支限界法求解0-1背包问题；2． 要求显示结果。

三、实验环境和工具：操作系统：Windows7开发工具：Eclipse3.7.1 jdk6开发语言：Java四、实验问题描述：0/1背包问题:现有n 种物品，对1<=i<=n ，第i 种物品的重量为正整数W i ，价值为正整数V i ，背包能承受的最大载重量为正整数C ，现要求找出这n 种物品的一个子集，使得子集中物品的总重量不超过C 且总价值尽量大。

动态规划算法描述: 根据问题描述，可以将其转化为如下的约束条件和目标函数：⎪⎩⎪⎨⎧≤≤∈≤∑∑==)1}(1,0{C max 11n i x x w x v ini i i ni ii寻找一个满足约束条件，并使目标函数式达到最大的解向量),......,,,(321n x x x x X =，使得C 1∑=≤n i i i x w ，而且∑=ni i i x v 1达到最大。

0-1背包问题具有最优子结构性质。

假设),......,,,(321n x x x x 是所给的问题的一个最优解，则),......,,(32n x x x 是下面问题的一个最优解：∑∑==⎪⎩⎪⎨⎧≤≤∈-≤n i i i ini i i x v n i x x w x w 2211max )2}(1,0{C 。

如果不是的话，设),......,,(32n y y y 是这个问题的一个最优解，则∑∑==>n i n i i i i i x v y v 22，且∑=≤+n i i i y w x w 211C 。

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背包问题，明显比动态规划法更优良。