实 验 报 告
课程名称： 算法设计与分析 实验名称：回溯法、分支限界法解0-1背包问题 任课教师： 张锦雄 专 业： 计算机科学与技术 班 级: 2007 级 1班 学 号： 姓 名： 蓝冠恒 完成日期： 2011年1月12日 一、实验目的： 掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。 二、主要实验内容及要求： 1．要求分别用回溯法和分支限界法求解0-1背包问题； 2．要求交互输入背包容量，物品重量数组，物品价值数组； 3．要求显示结果。 三、实验环境和工具： 操作系统:win7操作系统 开发工具：eclipse3.4、jdk1.6 开发语言：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;// 物品价值数组 double cw; // 当前重量 double cp; // 当前价值 double bestp; // 当前最优价值 /** * 回溯法解0-1背包问题。 * @param pp * 物品价值数组 * @param ww * 物品重量数组 * @param cc * 背包重量 * @return 最优价值 */ public double knapsack(double pp[], double ww[], double cc) { } // 回溯过程 private void backtrack(int i) { if (i > n) {// 达到叶节点 bestp = cp; } return; c = cc; n = pp.length; cw = 0.0; cp = 0.0; bestp = 0.0; Element[] q = new Element[n]; for (int i = 0; i < n; i++) { } Arrays.sort(q, new ElemComparator()); p = new double[n + 1]; w = new double[n + 1]; for (int i = 1; i <= n; i++) { } backtrack(1); return bestp; p[i] = pp[q[i - 1].id - 1]; w[i] = ww[q[i - 1].id - 1]; q[i] = new Element(i + 1, pp[i] / ww[i]); /** * 物体编号和单位重量价值载体。 * @author 蓝冠恒 */ public class Element { int id;// 编号 double d;// 单位重量价值 public Element(int id, double d) { this.id = id; } return bound; // 装满背包 if (i <= n) { } bound += p[i] * cleft / w[i]; // 以物品单位重量价值递减顺序装入物品 while (i <= n && w[i] <= cleft) { } cleft -= w[i]; bound += p[i]; i++; // 计算上界值 private double bound(int i) { double cleft = c - cw; double bound = cp; } if (bound(i + 1) > bestp) { } backtrack(1 + i); if (cw + w[i] <= c) { } cw += w[i]; cp += p[i]; backtrack(1 + i); cw -= w[i]; cp -= p[i]; } } this.d = d; /** * 比较器 * @author 蓝冠恒 */ public class ElemComparator implements Comparator