回溯法采用的是深度优先搜索，而分支限界采用的则是广度优先搜索。
分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
常见的有两种分支限界的方法:1.队列式分支限界法 2.优先队列式分支限界法
这里采用优先队列式分支限界法来解决01背包问题。
如背包容量为30，有三个物品质量分别为16,15,15，价值分别为45,25,25。
解空间树为:（盗的图）
代码如下:(Java实现)
import java.util.PriorityQueue; import java.util.Scanner; class PackNode implements Comparable<PackNode>{ int weight;//该节点目前背包中的重量 double value;//该节点目前背包中的总价值 double upValue;//该节点能够达到的价值上界 int Left; //该节点是否属于左节点 int level; //该节点是第几个物品的选择 PackNode father; //该节点的父节点 public int compareTo(PackNode node){ if(this.upValue<node.upValue) return 1; else if(this.upValue== node.upValue) return 0; else return -1; } } public class Knapsack0 { static int W;//箱子容量 static int n;//物品数量 static int []w;//物品重量 static double []v;//物品价值 static int maxValue;//最大的价值 static int[] bestWay;//最佳选择 static void getMaxValue(){ PriorityQueue<PackNode> pq = new PriorityQueue<PackNode>(); //构造一个初始化节点，属于-1层 PackNode initial = new PackNode(); initial.level = -1; for(int i=0;i<v.length;i++) initial.upValue+=v[i]; pq.add(initial); while(!pq.isEmpty()){ PackNode fatherNode = pq.poll(); if(fatherNode.level == n-1){ if(fatherNode.value > maxValue){ maxValue = (int)fatherNode.value; for(int i=n-1;i>=0;i--){ bestWay[i] = fatherNode.Left; fatherNode = fatherNode.father; } } } else{ //先统计其左节点信息，判断是否加入队列。 if(w[fatherNode.level+1]+fatherNode.weight <= W){ PackNode newNode = new PackNode(); newNode.level = fatherNode.level+1; newNode.value = fatherNode.value + v[fatherNode.level+1]; newNode.weight = w[fatherNode.level+1]+fatherNode.weight; newNode.upValue = Bound(newNode); newNode.father = fatherNode; newNode.Left = 1; if(newNode.upValue > maxValue) pq.add(newNode); } //向右节点搜索，其能够取到的价值上界通过父亲节点的上界减去本层物品的价值。 if((fatherNode.upValue - v[fatherNode.level+1])> maxValue){ PackNode newNode2 = new PackNode(); newNode2.level = fatherNode.level+1; newNode2.value = fatherNode.value; newNode2.weight = fatherNode.weight; newNode2.father = fatherNode; newNode2.upValue = fatherNode.upValue - v[fatherNode.level+1]; newNode2.Left = 0; pq.add(newNode2); } } } } //用于计算该节点的最高价值上界 static double Bound(PackNode node){ double maxLeft = node.value; int leftWeight = W - node.weight; int templevel = node.level; //尽力依照单位重量价值次序装剩余的物品 while(templevel <= n-1 && leftWeight > w[templevel] ){ leftWeight -= w[templevel]; maxLeft += v[templevel]; templevel++; } //不能装时，用下一个物品的单位重量价值折算到剩余空间。 if( templevel <= n-1){ maxLeft += v[templevel]/w[templevel]*leftWeight; } return maxLeft; } public static void main(String[] args){ Scanner input=new Scanner(System.in); System.out.println("箱子容量:"); W=input.nextInt(); System.out.println("物品数量:"); n=input.nextInt(); w=new int[n]; v=new double[n]; bestWay=new int[n]; System.out.println("每一件物品的重量:"); for(int i=0;i<n;i++){ w[i]=input.nextInt(); } System.out.println("每一件物品的价值:"); for(int i=0;i<n;i++){ v[i]=input.nextDouble(); } getMaxValue(); System.out.println("该背包能够取到的最大价值为:"+maxValue); System.out.println("所取物品:"); for(int i=0;i<bestWay.length;i++){ System.out.print(bestWay[i]+" "); } } }