当前位置:首页 >> 电子/电路 >>

回溯算法之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>(); int v[]={9,10,7,4}; int w[]={3,5,2,1};

PriorityQueue<object> pq=new PriorityQueue<object>();

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++) //开始算法 backtrack(1,objects,a);

vw[i]=pq.poll().getid();

}

//输出 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())//叶子 { return;

a.setmaxvaule(a.getvalue());

}

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 bound=a.getvalue(); int leftcontain=a.getmaxweight()-a.getcontain(); 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 return bound;

etweight();

}

}

import java.util.ArrayList;

public class bag {

private int contain; private int value; private int maxweight; private int maxvalue; public bag(int maxw){ this.contain=0; this.value=0; private ArrayList<object> objects;

this.maxweight=maxw; this.maxvalue=0; } this.objects=new ArrayList<object>();

public int getcontain(){return contain;} public int getvalue(){return value;}; public void addobject(object o){ this.objects.add(o); this.value+=o.getvalue(); }

public void resetcontain(int c){this.contain=c;} public void resetvalue(int v){this.value=v;}

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;} @Override

public int getweight(){return this.weight;}

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;

}

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


相关文章:
基于C#的0—1背包问题的回溯算法
龙源期刊网 http://www.qikan.com.cn 基于 C#的 0—1 背包问题的回溯算法 作者:陈自力 来源:《电脑知识与技术》2016 年第 36 期 摘要:0-1 背包问题是经典...
回溯法解决01背包问题
回溯法解决01背包问题 - 回溯法是一个既带有系统性又带有跳跃性的搜索算法。 它在包含问题的所有解的解空间树中按照 深度优先的策略,从根节点出发搜索解空间树。...
回溯法解0-1背包问题实验报告
回溯法解0-1背包问题实验报告_IT/计算机_专业资料。用回溯算法来解0-1背包问题的实验报告 实验4 一 、实验要求 回溯法解 0-1 背包问题 1.要求用回溯法...
回溯法实验(0-1背包问题)
回溯法实验(0-1背包问题)_IT/计算机_专业资料。算法分析与设计实验报告 第五 次附加实验姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法...
实验五:01背包问题的回溯算法设计
实验五:01背包问题回溯算法设计_计算机软件及应用_IT/计算机_专业资料。实验五:01背包问题回溯算法设计 算法 代码 结果截图 实验五:0/1 背包问题的回溯算法...
算法实验报告01背包问题
算法实验报告01背包问题 - hebut的,你懂得。动态规划、贪心算法回溯法三种方法的实现。仅供参考,有能力还是鼓励自己做
回溯法求01背包问题
回溯法求01背包问题_IT/计算机_专业资料。实验题目 给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值 为 vi,0/1 背包问题是如何选择装入...
用回溯法解决0-1背包问题
标签: 回溯法| 背包| 用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决0-1背包问题 #include&lt;stdio.h&gt; int c; //背包容量 ...
动态规划与回溯法解决0-1背包问题
五、算法测试代码: #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;iostream...二、总体思路: 01 背包属于找最优解问题,用回溯法需要构造解的子集树。在...
0-1背包问题的解决(回溯法)
0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题。 前面这块转贴原理及 c++代码实现的...
更多相关标签: