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

1、实 验 报 告 课程名称： 算法设计与分析 实验名称：回溯法、分支限界法解0-1背包问题任课教师： 张锦雄 专 业： 计算机科学与技术 班 级: 2007 级 1班 学 号： 姓 名： 蓝冠恒 完成日期： 2011年1月12日 一、实验目的：掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。 二、主要实验内容及要求：1 要求分别用回溯法和分支限界法求解0-1背包问题；2 要求交互输入背包容量，物品重量数组，物品价值数组；3 要求显示结果。 三、实验环境和工具：操作系统:win7操作系统开发工具：eclipse3.4、jdk1.6开发语言：

2、java四、实验结果与结论：（经调试正确的源程序和程序的运行结果）1.1、回溯法求解0-1背包问题源代码： package cn.lgh;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Comparator;/* * 回溯法解0-1背包问题。 * author 蓝冠恒 */public class BTKnapsack double c;/ 背包重量 int n; / 物品总数 double w;/ 物品重量数组 double p;/

3、物品价值数组 double cw; / 当前重量 double cp; / 当前价值 double bestp; / 当前最优价值/* * 回溯法解0-1背包问题。 * param pp * 物品价值数组 * param ww * 物品重量数组 * param cc * 背包重量 * return 最优价值 */public double knapsack(double pp, double ww, double cc) c = cc;n = pp.length;cw = 0.0;cp = 0.0;bestp = 0.0;Element q = new Elementn;for (int i

4、= 0; i < n; i+) qi = new Element(i + 1, ppi / wwi);Arrays.sort(q, new ElemComparator();p = new doublen + 1;w = new doublen + 1;for (int i = 1; i <= n; i+) pi = ppqi - 1.id - 1;wi = wwqi - 1.id - 1;backtrack(1);return bestp;/ 回溯过程private void backtrack(int i) if (i > n) / 达到叶节点bestp = cp;ret

5、urn;if (cw + wi <= c) cw += wi;cp += pi;backtrack(1 + i);cw -= wi;cp -= pi;if (bound(i + 1) > bestp) backtrack(1 + i);/ 计算上界值private double bound(int i) double cleft = c - cw;double bound = cp;/ 以物品单位重量价值递减顺序装入物品while (i <= n && wi <= cleft) cleft -= wi;bound += pi;i+;/ 装满背包if (i

6、 <= n) bound += pi * cleft / wi;return bound;/* * 物体编号和单位重量价值载体。 * author 蓝冠恒 */public class Element int id;/ 编号double d;/ 单位重量价值public Element(int id, double d) this.id = id;this.d = d;/* * 比较器 * author 蓝冠恒 */public class ElemComparator implements Comparator<Object> public int compare(Obje

7、ct object1, Object object2) Element element1 = (Element) object1;Element element2 = (Element) object2;if (element1.d < element2.d) return 1; else return 0;public static void main(String args) String input;String flag;double capacity = 0;double pp;double ww;double bestP=0.0;BTKnapsack btKnapsack=n

8、ew BTKnapsack();BufferedReader in = new BufferedReader(new InputStreamReader(System.in);do try do System.out.println("请选择数字功能键： 1-输入数据，2-退出系统");flag = in.readLine().trim(); while (!(flag.equals("1") | flag.equals("2");if (flag.equals("2") break;do System.out.p

9、rintln("请输入各物品重量，数据之间必须以顿号间隔分开！");input = in.readLine().trim();input = in.readLine().replaceAll(" ", ""); while (input.equals("");if(input.equals("2")break;String datas = input.split("、");int n1 = datas.length;pp=new doublen1;ww=new doublen

10、1;for (int i = 0; i < n1; i+) wwi= Double.parseDouble(datasi);do System.out.println("请输入各物品价值，数据之间必须以顿号间隔分开！");input = in.readLine().trim();input = in.readLine().replaceAll(" ", ""); while (input.equals("");if(input.equals("2")break;datas= input.s

11、plit("、");int n2 = datas.length;if(n1!=n2)System.out.println("输入数据个数不一致，重新输入");continue;for (int i = 0; i < n1; i+) ppi= Double.parseDouble(datasi);do System.out.println("请输入背包的容量：");input = in.readLine().trim();input = in.readLine().replaceAll(" ", "&

12、quot;); while (input.equals("");if(input.equals("2")break;capacity=Double.parseDouble(input);bestP=btKnapsack.knapsack(pp, ww, capacity);System.out.println("回溯法解得最优价值："+bestP); catch (Exception e) e.printStackTrace(); while (true);1.2、运行结果：2.1、分支限界法求解0-1背包问题源代码： package

13、 cn.lgh;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;/* * 分支界限法解0-1背包问题。 * author 蓝冠恒 */public class BBKnapsack double c;/ 背包重量int n; / 物品总数double w;/ 物品重量数组double p;/ 物品价值数组double cw; / 当前重量double cp; / 当前价值int bestx; / 最优解MaxHeap maxHeap = new MaxHeap();/

14、活节点优先队列/ 计算节点所对应的节点的上界private double bound(int i) double cleft = c - cw;double b = cp;/ 以物品单位重量价值递减装填剩余容量while (i <= n && wi <= cleft) cleft -= wi;b += pi;i+;/ 装填剩余容量装满背包if (i <= n) b += pi / wi * cleft;return b;/ 添加新的活节点到子集树和优先队列中private void addLiveNode(double upperProfit, double

15、pp, double ww,int level, BBnode parent, boolean leftChild) BBnode b = new BBnode(parent, leftChild);HeapNode node = new HeapNode(b, upperProfit, pp, ww, level);maxHeap.put(node);/ 优先队列式分支界限法private double bbKnapsack() BBnode enode = null;int i = 1;double bestp = 0.0;double up = bound(1);while (i !=

16、n + 1) double wt = cw + wi;/ 检查当前扩展节点的左儿子节点if (wt <= c) if (cp + pi > bestp) bestp = cp + pi;addLiveNode(up, cp + pi, cw + wi, i + 1, enode, true);up = bound(i + 1);/ 检查当前扩展节点的右儿子节点if (up >= bestp) addLiveNode(up, cp, cw, i + 1, enode, false);HeapNode node = maxHeap.removeMax();enode = node

17、.liveNode;cw = node.weight;cp = fit;up = node.upperProfit;i = node.level;/ 构造当前最优解for (int j = n; j > 0; j-) bestxj = (enode.leftChild) ? 1 : 0;enode = enode.parent;return cp;/* 将个物体依其单位重量价值从大到小排列，然后调用bbKnapsack完成对子集树优先队列式分支界*限搜索。 * * return 最优解 */public double knapsack(double pp, double

18、ww, double cc, int xx) c = cc;n = pp.length;Element q = new Elementn;double ws = 0.0;double ps = 0.0;for (int i = 0; i < n; i+) qi = new Element(i + 1, ppi / wwi);ps += ppi;ws += wwi;if (ws <= c) for (int i = 1; i <= n; i+) xxi = 1;return ps;/ 依单位重量价值排序Arrays.sort(q, new ElemComparator();p

19、= new doublen + 1;w = new doublen + 1;for (int i = 1; i <= n; i+) pi = ppqi - 1.id - 1;wi = wwqi - 1.id - 1;cw = 0.0;cp = 0.0;bestx = new intn + 1;maxHeap = new MaxHeap();/ 调用bbKnapsack求问题的最优解double maxp = bbKnapsack();for (int i = 1; i <= n; i+) xxqi - 1.id - 1 = bestxi;return maxp;public sta

20、tic void main(String arg) String input;String flag;double capacity = 0;double pp;double ww;int xx;double bestP=0.0;BBKnapsack bbKnapsack=new BBKnapsack();BufferedReader in = new BufferedReader(new InputStreamReader(System.in);do try do System.out.println("请选择数字功能键： 1-输入数据，2-退出系统");flag = i

21、n.readLine().trim(); while (!(flag.equals("1") | flag.equals("2");if (flag.equals("2") break;do System.out.println("请输入各物品重量，数据之间必须以顿号间隔分开！");input = in.readLine().trim();input = in.readLine().replaceAll(" ", ""); while (input.equals("

22、");if(input.equals("2")break;String datas = input.split("、");int n1 = datas.length;pp=new doublen1;ww=new doublen1;for (int i = 0; i < n1; i+) wwi= Double.parseDouble(datasi);do System.out.println("请输入各物品价值，数据之间必须以顿号间隔分开！");input = in.readLine().trim();input = i

23、n.readLine().replaceAll(" ", ""); while (input.equals("");if(input.equals("2")break;datas= input.split("、");int n2 = datas.length;if(n1!=n2)System.out.println("输入数据个数不一致，重新输入");continue;for (int i = 0; i < n1; i+) ppi= Double.parseDouble

24、(datasi);do System.out.println("请输入背包的容量：");input = in.readLine().trim();input = in.readLine().replaceAll(" ", ""); while (input.equals("");if(input.equals("2")break;xx=new intn1;capacity=Double.parseDouble(input);bestP=bbKnapsack.knapsack(pp, ww, ca

25、pacity, xx);System.out.println("分支界限法法解得最优价值："+bestP);System.out.println("各个被装入物品情况(1表示被装入，0表示未被装入)：");for (int i = 0; i < n1; i+) System.out.print(xxi+" ");System.out.println("n"); catch (Exception e) e.printStackTrace(); while (true);package cn.lgh;/* * 分

26、支界限节点 * author 蓝冠恒 */public class BBnode BBnode parent;/父节点boolean leftChild;/左孩子标识public BBnode( BBnode parent,boolean leftChild) this.parent=parent;this.leftChild=leftChild;package cn.lgh;import java.util.Comparator;/* * Element对象比较器 * author 蓝冠恒 */public class ElemComparator implements Comparator

27、<Object>public int compare(Object object1, Object object2) Element element1 = (Element)object1;Element element2 = (Element)object2;if (element1.d< element2.d) return 1; else return 0;package cn.lgh;/* * 物品编号和单位重量价值载体。 * author 蓝冠恒 */public class Element int id;/物品编号double d;/单位重量价值public El

28、ement(int id,double d) this.id=id;this.d=d;package cn.lgh;import java.util.Comparator;/* * 堆节点比较器。 * author 蓝冠恒 */public class HeapComparator implements Comparator<Object>public int compare(Object object1, Object object2) HeapNode heapNode1 = (HeapNode)object1;HeapNode heapNode2 = (HeapNode)ob

29、ject2;if (heapNode1.upperProfit< heapNode2.upperProfit) return 1; else return 0;package cn.lgh;/* *堆节点* author 蓝冠恒 */public class HeapNode BBnode liveNode; / 活节点double upperProfit; / 节点价值上限double profit; / 节点所对应的价值double weight; / 节点所对应的重量int level; / 活节点在子集树中所处的层次序号/ 构造方法public HeapNode(BBnode li