当前位置:首页 >> 计算机软件及应用 >>

回溯算法之01背包问题java源程序


实验报告 11
课程 数据结构与算法 实验名称 班级 11 计本 学号 回溯法 105032011130 第 姓名 页 风律澈

实验日期:2013 年 5 月 20 日

报告退发 (订正 、 重做)

一、实验目的
掌握回溯法的原理和应用。

二、实验环境
1、微型计算机一台 2、WINDOWS 操作系统,Java SDK,Eclipse 开发环境

三、实验内容
必做题: 1、编写程序,实现n后问题算法。(如果上周没完成,这周完成) 2、编写程序,采用回溯法实现0-1背包问题。

四、实验步骤和结果
(附上代码和程序运行结果截图) 2、0-1 回溯背包问题
import java.util.ArrayList; import java.util.PriorityQueue;

public class main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stu //初始化工作 bag a=new bag(7); ArrayList<object> objects=new ArrayList<object>(); PriorityQueue<object> pq=new PriorityQueue<object>(); int v[]={9,10,7,4}; int w[]={3,5,2,1}; for(int i=0;i<v.length;i++){ pq.add(new object(v[i],w[i])); objects.add(new object(v[i],w[i])); } //生成单位价值排序数组,将物品以单位价值从高到低排列,记录数组 int vw[]=new int[v.length];

for(int i=0;i<v.length;i++) vw[i]=pq.poll().getid(); //开始算法 backtrack(1,objects,a); //输出 System.out.println(a.getmaxvalue()); } private static void backtrack(int i,ArrayList<object> objects,bag a) { // TODO Auto-generated method stub if(i>objects.size())//叶子 { a.setmaxvaule(a.getvalue()); return; } if(a.getcontain()+objects.get(i-1).getweight()<=a.getmaxweight()) { a.addobject(objects.get(i-1)); backtrack(i+1,objects,a); a.removeobjec(objects.get(i-1)); } if(bound(i+1,objects,a)>a.getmaxvalue()){ backtrack(i+1,objects,a); } } private static int bound(int i,ArrayList<object> objects,bag a) { // TODO Auto-generated method stub int leftcontain=a.getmaxweight()-a.getcontain(); int bound=a.getvalue(); while((i<=objects.size())&& (objects.get(i-1).getweight()<=leftcontain)) { leftcontain-=objects.get(i-1).getweight(); bound+=objects.get(i-1).getvalue(); i++; } if(i<=objects.size()) bound+=objects.get(i-1).getvalue()*leftcontain/objects.get(i-1).g etweight(); return bound;

} } import java.util.ArrayList;

public class bag { private int contain; private int value; private int maxweight; private int maxvalue; private ArrayList<object> objects; public bag(int maxw){ this.contain=0; this.value=0; this.maxweight=maxw; this.maxvalue=0; this.objects=new ArrayList<object>(); } public int getcontain(){return contain;} public void resetcontain(int c){this.contain=c;} public int getvalue(){return value;}; public void resetvalue(int v){this.value=v;} public void addobject(object o){ this.objects.add(o); this.value+=o.getvalue(); this.contain+=o.getweight(); } public void removeobjec(object o){ this.objects.remove(o); this.value-=o.getvalue(); this.contain-=o.getweight(); } public int getmaxvalue(){return this.maxvalue;} public void setmaxvaule(int max){this.maxvalue=max;} public int getmaxweight(){return this.maxweight;} } public class object implements Comparable<object>{ private static int ids; private int id; private int value; private int weight; public object(int v,int w){

ids++; this.id=ids; this.value=v; this.weight=w; } public int getid(){return id;} public int getvalue(){return this.value;} public int getweight(){return this.weight;} @Override public int compareTo(object o) { // TODO Auto-generated method stub if((this.value/this.weight)>(o.value/o.weight))return -1; if((this.value/this.weight)<(o.value/o.weight))return 1; return 0; } }

五、实验总结
(本次实验完成的情况,心得体会)


相关文章:
回溯算法之01背包问题JAVA源程序.pdf
回溯算法之01背包问题JAVA源程序 - 实验报告 11 课程 数据结构与算法
回溯算法之01背包问题java源程序.doc
回溯算法之01背包问题java源程序 - 实验报告 11 课程 数据结构与算法
回溯法解决01背包问题.doc
回溯法解决01背包问题 - 回溯法是一个既带有系统性又带有跳跃性的搜索算法。 它
分支限界算法之0 1背包问题和单源最短路径问题JAVA源程序.pdf
1背包问题和单源最短路径问题JAVA源程序_电子/电路...public class bag01do { /** * @param args *...分别用回溯法和分支限界... 8页 2下载券 ...
算法分析与程序设计动态规划及回溯法解01背包问题.doc
算法分析与程序设计动态规划及回溯法01背包问题 - 动态规划法、回溯法0-1 背包问题 2012 级 计科 庞佳奇 一、 1. 问题描述与分析 动态规划算法通常用于...
01背包问题回溯算法.doc
01背包问题回溯算法 - 假设有 7 个物品,它们的重量和价值如下表所示。若这些
回溯法解决01背包问题_图文.ppt
回溯法解决01背包问题 - 回溯法解决01背包问题 回溯法解决01背包问题 1、算法思想 2、问题描述 3、设计实现 回溯法解决01背包问题 回溯法:是一个既带有系统性又...
回溯法01背包问题_图文.ppt
回溯法01背包问题 - 回溯法解决01背包问题 1、算法思想 2、问题描述 3、设计实现 回溯法01背包问题 回溯法:是一个既带有系统性又带有跳跃性的的 搜索算法。它...
动态规划解决算法0-1背包问题实验报告(含源代码).doc
动态规划解决算法0-1背包问题实验报告(含源代码)_计算机软件及应用_IT/计算机_...2.掌握动态规划、贪心算法回溯法、分支限界法的原理,并能够按其原理 编程实现...
回溯算法解决0-1背包问题(DOC).doc
《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称:回溯算法解决 0-1 背包问题 实验日期:...
回溯法、分支限界法解0-1背包问题(计算机算法设计与分....doc
回溯法求解 0-1 背包问题源代码: package cn.lgh; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java....
回溯法实验0 1背包问题 C++.doc
knapsack(v,w,c,n,m); traceback(m,w,c,n,x); } 0-1 背包问题程序...01背包问题回溯法求解... 7页 1下载券 0-1背包问题的解决(回溯... 7...
实验五:01背包问题的回溯算法设计.doc
实验五:01背包问题回溯算法设计_计算机软件及应用_IT/计算机_专业资料。实验五:01背包问题回溯算法设计 算法 代码 结果截图 实验五:0/1 背包问题的回溯算法...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题_电脑基础知识_IT/计算机_专业资料。一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/...
0029算法笔记【回溯法】n后问题和0-1背包问题.doc
0029算法笔记【回溯法】n后问题和0-1背包问题_计算机软件及应用_IT/计算
算法分析与设计01背包递归回溯.doc
算法分析与设计01背包递归回溯 - 算法分析与设计 实验 03 实验目的 ? ? ? ? 掌握动态规划算法,简单 0-1 背包问题; 掌握最优二叉搜索树的算法。 掌握贪心算法...
回溯法求01背包问题.doc
回溯法01背包问题_IT/计算机_专业资料。实验题目 给定 n 种物品和一个容
回溯法01背包问题.doc
回溯法01背包问题 - 核心源代码 #include <iostream.
01背包问题不同算法设计、分析与对比报告.doc
("背包中物品的最大总价值为" + value); } } 回溯法: public class Back...import java.util.ArrayList; public class bag01do { public static void main...
回溯法实验(0-1背包问题).doc
回溯法实验(0-1背包问题)_IT/计算机_专业资料。算法分析与设计实验报告 第五 次附加实验姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法...
更多相关标签: