实验八 背包问题和最优二叉搜索树算法设计 信科 06 李婕
宁夏师范学院数学与计算机科学学院
《算法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
与设计》
实验报告
化学实验报告单总流体力学实验报告观察种子结构实验报告观察种子结构实验报告单观察种子的结构实验报告单
实验项目名称:0-1背包问题和最优二叉搜索树算法设计 实验序号:8
学 号 23 姓 名 专业、班 10级信科班 实验地318 指导教惠云 时间 2013、5、23 点 师
一、实验目的及要求
(1) 掌握使用动态规划方法设计0-1背包问题的算法;
(2) 掌握使用动态规划方法设计最优二叉搜索树问题的算法; 二、实验设备(环境)及要求
1、环境要求:
硬件:PC(PII以上，128M以上内存)、因特网接入;
软件:Windows XP操作系统、VC++6.0编程环境。
2、实验要求:
(1) 独立完成实验，源代码书写
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
;
(2) 程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确;
(3) 实验完成后必须有实验结果的分析及本次实验的总结。 三、实验内容与步骤
(1) 设计求解0-1背包问题的程序，并将装入背包的物品的最大价值及最优解在屏幕上显示。
public class Demo1 {
public static void main(String[] args){
Object p1 = new Object();
Object p2 = new Object();
Object p3 = new Object();
Object p4 = new Object();
Method m = new Method(p1,p2,p3,p4);
p1.chushihua(3,4);
p2.chushihua(2,3);
p3.chushihua(2,5);
p4.chushihua(4,5);
m.sortObject(m.arr,4);
m.knaspsack(m.arr,4);
m.print(m.arr,4); }
}
class Object{
int value;
int weight;
float avevalue;
float num;
void chushihua(int value,int weight){
this.value = value;
this.weight = weight;
this.avevalue = ((float)value/(float)weight);}
}
class Method extends Object{
Object arr[] = new Object[4];
Method(Object p1,Object p2,Object p3,Object p4){ //将4个物品引用存放在一
个数组中
arr[0] = p1;
arr[1] = p2;
arr[2] = p3;
arr[3] = p4;}
void sortObject(Object a[],int n){ //按物品平均价值排序,n为物品个数
for(int i = 0;i < n-1; i++){
for(int j = 0;j < n-i-1; j++){
if(a[j].avevalue < a[j+1].avevalue){
Object temp;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;}
}
}
}
void knaspsack(Object b[],int n){
//v为背包容量，n为物品数
int c = 15; //背包容量
for(int i = 0;i < n; i++){
b[i].num = 0;
if(b[i].weight > c){
b[i].num = (float)c/(float)(b[i].weight);
break;}
else{
b[i].num = 1;
c -= b[i].weight; } }}
void print(Object c[],int n){
for(int i = 0;i < n; i++){
System.out.println("价格为"+c[i].value+","+"重量为"+c[i].weight+"的
物品放入"+c[i].num+"件"); } }}
(2). 设计求解最优二叉搜索树问题的程序，并将最优二叉搜索树的最短平均路
径、最优二叉搜索树在屏幕上显示。 四、实验结果与数据处理
五、分析与讨论
1、分析求解0-1背包问题算法的时间复杂度。
n2求解0-1背包问题算法的时间复杂度为O(min{nc,})。
2. 分析求解最优二叉搜搜树算法的时间复杂度。
n2解最优二叉搜搜树算法的时间复杂度为O()。 六、教师评语
成绩
签名:
日期: 年 月 日
浙公网安备 33021202002483