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

实验报告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 objects=new ArrayList();PriorityQueue pq=new PriorityQueue();int v=9,10,7,4;int w=3,5,2,1;for(int i=0;iv.length;i+)pq.add(new object(vi,wi);objects.add(new object(vi,wi);/生成单位价值排序数组，将物品以单位价值从高到低排列，记录数组int vw=new intv.length;for(int i=0;iv.length;i+)vwi=pq.poll().getid();/开始算法backtrack(1,objects,a);/输出System.out.println(a.getmaxvalue();private static void backtrack(int i,ArrayList objects,bag a) / TODO Auto-generated method stubif(iobjects.size()/叶子a.setmaxvaule(a.getvalue();return;if(a.getcontain()+objects.get(i-1).getweight()a.getmaxvalue()backtrack(i+1,objects,a);private static int bound(int i,ArrayList objects,bag a) / TODO Auto-generated method stubint 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).getweight();return bound;import java.util.ArrayList;public class bag private int contain;private int value;private int maxweight;private int maxvalue;private ArrayList objects;public bag(int maxw)this.contain=0;this.value=0;this.maxweight=maxw;this.maxvalue=0;this.objects=new ArrayList();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 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;Overridepublic int compareTo(object o) / TODO Auto-generated method stubif