背包问题回溯法回朔法、分支限界法解0-1背包问题程序，要完整的，可执行的。限JAVA或C语言编写

用回溯法做0-1背包问题，这两行（程序中标注）是干嘛？为什么又要减？

看来新手对于回溯还是比较难以理解的，其实很简单啊 ，就是一个递归啊，递归啊楼主就是自己调用自己啊，自己调用自己啊，你初中就学过了啊。

比如 f[i] = f[i-1] + 3; 好了现在我跟你说f[0] = 1 , 那么f[10]怎么求呢，就是不断的迭代那个公式啊，写成代码就是 int?f(int?i) { ????if(i?==?0)?return?1; ????return?f[i-1]?+?3; }i = 0 是整个递归的边界，就是到i = 0 的时候不继续迭代了，直接返回了，然后一层一层返回。

比如求f(2) = f(1) + 3 = (f(0)+3) +3 ,其中f[0] = 1,好了不断往左迭代就能算出f(2)了。

好了我知道楼主要说我废话了，想说你问的又不是这个是吧，但是真的无关了？ 我们再来看看你给的代码吧 void?backtrack(int?i) { ????double?bound(int?j);?//声明后面要用到的限界函数 ????//到达叶子结点 ????if(i>n)//这个就是边界，因为这边他没有调用自己而是直接返回了， ????对应了我们上面的i?=?0；递归一定要有边界！ ????{ ???????bestp=cp; ???????return; ????} ????//当不是边界的时候呢，既然是递归那肯定就是自己调自己了 ????if(cw+w[i]<=c) ????{ ????????cw+=w[i]; ????????cp+=p[i]; ????????put[i]=1; ????????backtrack(i+1);//这边就在自己调用自己了，下边那个backtrack(i+1)也一样 ????????cw-=w[i];//好了楼主的问题来了，这边在干吗？好了要知道这边在干吗，必须要知道这条语句什么时候执行啊！那么这条语句什么时候执行呢？当然是上面那条语句执行完毕之后执行啊，楼主也看到了上面是个递归函数，对应到我们上面的递推公式，他要一直自己调用自己啊，直到边界。

那么在这个函数里，边界就是上面的i>n，那么究竟是什么意思呢？也就是说这执行这条语句之前，我都已经搜索到叶子节点了，而且已经返回了，就是说当取了第i这个物品的时候呢，后面所有的情况我都已经处理完了。

那么我是不是该处理当不取第i这个物品了呢，那么我就要把刚刚取了第i个物品的重量和价值减掉，因为我现在要处理的是不取他们，所以这边把刚刚加的给减掉还了，这就是所谓的回溯，楼主好好体会一下，其实没有那么复杂的，你想啊backtrack(int?i)这个函数是在干吗，不就是计算以i为父节点的子树能取到的最大价值么，那么backtrack(i+1)就是计算以i+1为父节点的子树能取到的最大值啊。

那么我取了i节点去计算一下backtrack(i+1)，然后我在不取i节点去计算一下backtrack(i+1)，整个程序大概就是这个思想，你的问题就是在不取i节点的时候把当时取i节点的加上去的值减掉还原成不取i节点时的情况，这也是回溯的中心思想。

其实你还可以这么分析：假设这边只有两层，也就是说只有2件物品，那么是不是很好跟踪程序呢，这叫降低规模。

????????cp-=p[i];// ????} ????//符合条件才搜索右子树 ????if(bound(i+1)>bestp) ????????backtrack(i+1); }

背包问题的算法

3.2 背包问题 背包问题有三种 1.部分背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。

解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止. 2.0/1背包 一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

<1>分析说明: 显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制). 程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。

按递归的思想我们可以把问题分解为子问题,使用递归函数 设 f(i，x)表示前i件物品，总重量不超过x的最优价值 则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x）） f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0; 动态规划方法(顺推法)程序如下: 程序如下： program knapsack02; const maxm=200;maxn=30; type ar=array[1..maxn] of integer; var m,n,j,i:integer; c,w:ar; f:array[0..maxn,0..maxm] of integer; function max(x,y:integer):integer; begin if x>y then max:=x else max:=y; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); for i:=1 to m do f(0,i):=0; for i:=1 to n do f(i,0):=0; for i:=1 to n do for j:=1 to m do begin if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j]) else f[i,j]:=f[i-1,j]; end; writeln(f[n,m]); end. 使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。

3.完全背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn, 每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多. 求旅行者能获得的最大总价值。

本问题的数学模型如下： 设 f(x)表示重量不超过x公斤的最大价值， 则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n 程序如下:（顺推法） program knapsack04; const maxm=2000;maxn=30; type ar=array[0..maxn] of integer; var m,n,j,i,t:integer; c,w:ar; f:array[0..maxm] of integer; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); f(0):=0; for i:=1 to m do for j:=1 to n do begin if i>=w[j] then t:=f[i-w[j]]+c[j]; if t>f[i] then f[i]:=t end; writeln(f[m]); end.

回朔法、分支限界法解0-1背包问题程序，要完整的，可执行的。限JAVA或C语言编写

Java回溯法： package sun; import java.util.*; public class Knapsack0{ /* 用回溯法解决0-1背包问题 */ private double[] p,w;//分别代表价值和重量 private int n; private double c,bestp,cp,cw; private int x[]; //记录可选的物品 private int[] cx; public Knapsack0(double pp[],double ww[],){ this.p=pp;this.w=ww;this.n=pp.length-1; ;this.cp=0;this.cw=0; this.bestp=0; x=new int[ww.length]; cx=new int[pp.length]; } void knapsack(){ backtrack(0); } void backtrack(int i){ if(i>n){ //判断是否到达了叶子节点 if(cp>bestp){ for(int j=0;j<x.length;j++) x[j]=cx[j]; bestp=cp; } return; } if(cw+w[i]<=c){//搜索右子树 cx[i]=1; cw+=w[i]; cp+=p[i]; backtrack(i+1); cw-=w[i]; cp-=p[i]; } cx[i]=0; backtrack(i+1); //检查左子树 } void printResult(){ System.out.println("*****回溯法*****"); System.out.println("*****物品个数：n=5"); System.out.println("*****背包容量：c=10"); System.out.println("*****物品重量数组：ww= {2,2,6,5,4}"); System.out.println("*****物品价值数组：vv= {6,3,5,4,6}"); System.out.println("*****最优值：="+bestp); System.out.println("*****选中的物品是:"); for(int i=0;i<x.length;i++){ System.out.print(x[i]+" "); } } public static void main(String[] args){ double p[]={6,3,5,4,6}; double w[]={2,2,6,5,4}; int maxweight=10; Knapsack0 ks=new Knapsack0(p,w,maxweight); ks.knapsack(); //回溯搜索 ks.printResult(); } } 分支限界法： package sun; public class knapsack1 { static double c; static int n; static double w[]; static double p[]; static double cw; static double cp; static int bestX[]; static MaxHeap heap; //上界函数bound计算结点所相应价值的上界 private static 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将一个新的活结点插入到子集树和优先队列中 private static void addLiveNode(double up,double pp,double ww,int lev,BBnode par,boolean ch){ //将一个新的活结点插入到子集树和最大堆中 BBnode b=new BBnode(par,ch); HeapNode node =new HeapNode(b,up,pp,ww,lev); heap.put(node); } private static double MaxKnapsack(){ //优先队列式分支限界法，返回最大价值，bestx返回最优解 BBnode enode=null; 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 =(HeapNode)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; } public static double knapsack(double pp[],double ww[],,int xx[]){ //返回最大值，bestX返回最优解 ; n=pp.length-1; //定义以单位重量价值排序的物品数组 Element q[]=new Element[n]; double ws=0.0; double ps=0.0; for(int i=0;i<n;i++){ q[i]=new 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; } public static void main(String [] args){ double w[]=new double[6]; w[1]=2;w[2]=2;w[3]=6;w[4]=5;w[5]=4; double v[]=new double[6]; v[1]=6;v[2]=3;v[3]=4;v[4]=5;v[5]=6; double c=10; int x[] = new int[6]; double m = knapsack(v,w,c,x); System.out.println("*****分支限界法*****"); System.out.println("*****物品个数：n=5"); System.out.println("*****背包容量：c=10"); System.out.println("*****物品重量数组：w= {2,2,6,5,4}"); System.out.println("*****物品价值数组：v= {6,3,5,4,6}"); System.out.println("*****最优值：="+m); System.out.println("*****选中的物品是:"); for(int i=1;i<=5;i++) System.out.print(x[i]+" "); } } //子空间中节点类型 class BBnode{ BBnode parent;//父节点 boolean leftChild;//左儿子节点标志 BBnode(BBnode par,boolean ch){ parent=par; leftChild=ch; } } class HeapNode implements Comparable{ BBnode liveNode; // 活结点 double upperProfit; //结点的价值上界 double profit; //结点所相应的价值 double weight; //结点所相应的重量 int level; // 活结点在子集树中所处的层次号 //构造方法 public HeapNode(BBnode node, double up, double pp , double ww,int lev){ liveNode = node; upperProfit = up; profit = pp; weight = ww; level = lev; } public pareTo(Object o) { double xup = ((HeapNode)o).upperProfit; if(upperProfit < xup) return -1; if(upperProfit == xup) return 0; else return 1; } } class Element implements Comparable{ int id; double d; public Element(int idd,double dd){ id=idd; d=dd; } public pareTo(Object x){ double xd=((Element)x).d; if(d<xd)return -1; if(d==xd)return 0; return 1; } public boolean equals(Object x){ return d==((Element)x).d; } } class MaxHeap{ static HeapNode [] nodes; static int nextPlace; static int maxNumber; public MaxHeap(int n){ maxNumber = (int)Math.pow((double)2,(double)n); nextPlace = 1;//下一个存放位置 nodes = new HeapNode[maxNumber]; } public static void put(HeapNode node){ nodes[nextPlace] = node; nextPlace++; heapSort(nodes); } public static HeapNode removeMax(){ HeapNode tempNode = nodes[1]; nextPlace--; nodes[1] = nodes[nextPlace]; heapSort(nodes); return tempNode; } private static 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; } private static void heapSort(HeapNode [] nodes){ for(int i=(nextPlace-1)/2;i>0;--i){ heapAdjust(nodes,i,nextPlace-1); } } } 不知道你是哪的学生， 此乃郑州轻工业学院考试试题， 并且还未上交， 抄的时候小心点， 参考一下就可以了， 不要全抄， 版权所有违者必究！！！！！！！！！ 哈哈哈哈 ！！！