1、如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。【概要设计】01背包问题是一个子集选取问题，适合
2、于用子集树表示01背包问题的解空间。在搜索解空间树是，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。int c;/背包容量int n; /物品数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前重量int cp;/当前价值int bestp;/当前最优值int *bestx;/当前最优解int *x;/当前解int Knap:Bound（int i）/计算上界void Knap:Backtrack（int i）/回溯int Knapsack（int p,int w,int c,int n） /为Kna
3、p:Backtrack初始化【详细设计】#includeusing namespace std;class Knapfriend int Knapsack（int p,int w,int c,int n ）;public:void print（）for（int m=1;m=n;m+）coutbestxm ;endl;private:int Bound（int i）;void Backtrack（int i）;Bound（int i）/计算上界int cleft=c-cw;/剩余容量int b=cp;/以物品单位重量价值递减序装入物品while（i=n&wi=cleft）cleft-=wi;b+
4、=pi;i+;/装满背包if（in）if（bestpcp）for（int j=1;jj+）bestxj=xj;bestp=cp;return;if（cw+wibestp）/搜索右子树xi=0;class Objectfriend int Knapsack（int p,int w,int c,int n）;int operator=a.d）;int ID;float d;int Knapsack（int p,int w,int c,int n）/为Knap:int W=0;int P=0;int i=1;Object *Q=new Objectn;for（i=1;ii+）Qi-1.ID=i;Qi
5、-1.d=1.0*pi/wi;P+=pi;W+=wi;if（W=c）return P;/装入所有物品/依物品单位重量排序float f;for（ i=0;n;for（int j=i;if（Qi.dp=new intn+1;w=new intn+1;p0=0;w0=0;请输入个背包的价值：pi;请输入个背包的重量：wi;请输入背包容量：c;Knapsack（p,w,c,n）N-1）cp） bestp=cp;elseif（ct=m）cp+=vt;m-=ct;knap（c,v,t+1,m）;m+=ct;cp-=vt;main（）int c=2,2,6,5,4,v=6,3,5,4,6;int m=10;knap（c,v,0,m）;printf（%dn,bestp）;
