- 1、本文档共15页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
实 验 报 告
课程名称: 算法设计与分析 实验名称:回溯法、分支限界法解0-1背包问题
任课教师: 张锦雄 专 业: 计算机科学与技术
班 级: 2007 级 1班 学 号:
姓 名: 蓝冠恒 完成日期: 2011年1月12日
一、实验目的:
掌握回溯法、分支限界法的原理,并能够按其原理编程实现解决0-1背包问题,以加深对回溯法、分支限界法的理解。
二、主要实验内容及要求:
要求分别用回溯法和分支限界法求解0-1背包问题;
要求交互输入背包容量,物品重量数组,物品价值数组;
要求显示结果。
三、实验环境和工具:
操作系统: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) {
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++) {
q[i] = new Element(i + 1, pp[i] / ww[i]);
}
Arrays.sort(q, new ElemComparator());
p = new double[n + 1];
w = new double[n + 1];
for (int i = 1; i = n; i++) {
p[i] = pp[q[i - 1].id - 1];
w[i] = ww[q[i - 1].id - 1];
}
backtrack(1);
return bestp;
}
// 回溯过程
private void backtrack(int i) {
if (i n) {// 达到叶节点
bestp = cp;
return;
}
if (cw + w[i] = c) {
cw += w[i];
cp += p[i];
backtrack(1 + i);
cw -= w[i];
cp -= p[i];
}
if (bound(i + 1) bestp) {
backtrack(1 + i);
}
}
// 计算上界值
private double bound(int i) {
double cleft = c - cw;
double bound = cp;
// 以物品单位重量价值递减顺序装入物品
while (i = n w[i] = cleft) {
cleft -= w[i];
bound += p[i];
i++;
}
// 装满背包
if (i = n) {
bound += p[i] * cleft / w[i];
}
return bound;
}
/**
* 物体编号和单位重量价值载体。
* @author 蓝冠恒
*/
pub
文档评论(0)