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

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

(附上代码和程序运行结果截图) 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背包问题回溯算法
01背包问题回溯算法 - 假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均不能 被分割,且背包容量 M=150,使用回溯方法求解此背包问题。请写 出状态...

01背包问题不同算法设计、分析与对比
01背包问题不同算法设计、分析与对比 - 实践动态规划、贪心、回溯以及分支限界算法程序设计
0-1背包问题的解决(回溯法)
0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题。 前面这块转贴原理及 c++代码实现的...