# 01背包问题不同算法设计、分析与对比报告

O（2n） O（n2n） O（2n）

5.需要提交不同算法的实现代码和总结报告。 动态规划方法：
public class Knapsack { public static void main(String[] args) { int[] value = { 0, 60, 100, 120 }; int[] weigh = { 0, 10, 20, 30 }; int weight = 50; Knapsack1(weight, value, weigh);

} public static void Knapsack1(int weight, int[] value, int[] weigh) { int[] v = new int[value.length]; int[] w = new int[weigh.length]; int[][] c = new int[value.length][weight + 1]; int d[] = new int [100]; for (int i = 0; i < value.length; i++) { v[i] = value[i]; w[i] = weigh[i]; } for (int i = 1; i < value.length; i++) { for (int k = 1; k <= weight; k++) { if (w[i] <= k) { c[i][k] = max(c[i - 1][k], c[i - 1][k - w[i]] + v[i]); } else { c[i][k] = c[i - 1][k]; } } } System.out.println(c[value.length - 1][weight]); } private static int max(int i, int j) { int k = i > j ? i : j; return k; } }

public class GreedyKnapSack { public static void main(String[] args) { int[] value = { 0, 60, 100, 120 }; int[] weigh = { 0, 10, 20, 30 }; int weight = 50; Knapsack1(weight, value, weigh); } private static void Knapsack1(int weight, int[] v, int[] w) { int n = v.length; double[] r = new double[n]; int[] index = new int[n]; for(int i = 0;i < n; i++) { r[i] = (double)v[i] / (double)w[i];

index[i] = i; } //按单位重量价值 r[i]=v[i]/w[i]降序排列 double temp = 0; for(int i = 0;i < n-1;i++){ for(int j = i+1;j < n;j++){ if(r[i] < r[j]){ temp = r[i]; r[i] = r[j]; r[j] = temp; int x = index[i]; index[i] = index[j]; index[j] = x; } } } //排序后的重量和价值分别存到 w1[]和 v1[]中 int[] w1 = new int[n]; int[] v1 = new int[n]; for(int i = 0;i < n;i++){ w1[i] = w[index[i]]; v1[i] = v[index[i]]; } System.out.println (Arrays.toString(w1)); System.out.println (Arrays.toString(v1)); int s=0;//包内现存货品的重量 int value=0;//包内现存货品总价值 for(int i = 0; i < n;i++){ if(s + w1[i] < weight){ value += v1[i]; s += w1[i]; } } System.out.println("背包中物品的最大总价值为" + value); } }

public class BacktrackKnapSack { public static void main(String[] args) { int[] value = { 0, 60, 100, 120 }; int[] weigh = { 0, 10, 20, 30 }; int weight = 50; Knapsack1(weight, value, weigh); }

private static void Knapsack1(int weight, int[] v, int[] w) { int n = v.length; double[] r = new double[n]; int[] index = new int[n]; for(int i = 0;i < n; i++) index[i] = i; } //按单位重量价值 r[i]=v[i]/w[i]降序排列 double temp = 0; for(int i = 0;i < n-1;i++){ for(int j = i+1;j < n;j++){ if(r[i] < r[j]){ temp = r[i]; r[i] = r[j]; r[j] = temp; int x = index[i]; index[i] = index[j]; index[j] = x; } } } //排序后的重量和价值分别存到 w1[]和 v1[]中 int[] w1 = new int[n]; int[] v1 = new int[n]; for(int i = 0;i < n;i++){ w1[i] = w[index[i]]; v1[i] = v[index[i]]; } //调用函数 KnapSackBackTrack()，输出打印装完物品以后的最大价值 KnapSackBackTrack(w1,v1,w1.length,weight); } private static void KnapSackBackTrack(int[] w1, int[] v1, int length, int weight) { int CurrentWeight = 0; int CurrentValue = 0; int maxValue = 0; int i = 0; int n = v1.length; while(i >= 0){ if(CurrentWeight + w1[i] < weight){ CurrentWeight += w1[i]; { r[i] = (double)v[i] / (double)w[i];

CurrentValue += v1[i]; i++; } else break; } if(i < n){ maxValue = CurrentValue; System.out.println("1 背包中物品的最大总价值为" + maxValue); } } }

package bag01b; import java.util.ArrayList;
public class bag01do { public static void main(String[] args) { // TODO Auto-generated method stub ArrayList<object> objects=new ArrayList<>(); objects.add(new object(10,60)); objects.add(new object(20,100)); objects.add(new object(30,120)); bag b=new bag(50,objects); b.findmaxvalue(); b.show(); } }

----------------------------------------------------------------------package bag01b; import java.util.ArrayList; import java.util.Collections; import java.util.PriorityQueue; public class private private private private bag { int bagv; ArrayList<object> objects; int maxvalue; ArrayList<object> result_objects;

public bag(int v,ArrayList<object> o){

super(); this.bagv=v; this.objects=o; this.maxvalue=0; this.result_objects=null; Collections.sort(objects); } public void show(){ System.out.println("maxvalue :"+ this.maxvalue); System.out.println("the object maxvalue:"+this.result_objects); }

when

public void findmaxvalue(){ PriorityQueue<Node> enode=new PriorityQueue<>(); Node node=new Node(0,null,bagv,this.objects); enode.offer(node); while(true){ if(enode.isEmpty()) break; node=enode.poll(); if(node.isend()){ this.maxvalue=node.get_bag_value(); this.result_objects=new ArrayList<>(node.get_in_bag_object()); return; } int i=node.get_node_in(); object iobject=this.objects.get(i); if(node.get_bag_weight()+iobject.getweight()<=this.bagv){ ArrayList<object> newnodeinbag=new ArrayList<object>(node.get_in_bag_object()); newnodeinbag.add(iobject); int newnodebagv=node.get_bag_leftv()-iobject.getweight(); Node newnode=new Node(i+1,newnodeinbag,newnodebagv,this.objects); enode.add(newnode); if(newnode.get_bag_value()>this.maxvalue){ this.maxvalue=newnode.get_bag_value(); this.result_objects=new ArrayList<>(newnode.get_in_bag_object()); } }

Node newnode=new Node(i+1,node.get_in_bag_object(),node.get_bag_leftv(),this.objects); if(newnode.get_bag_prio()>this.maxvalue) enode.add(newnode); } } } ----------------------------------------------------------------------package bag01b; import java.util.ArrayList; public class Node implements Comparable<Node>{ private int node_in; private ArrayList<object> inbag_object; private ArrayList<object> outbag_object; private int leftv; private int prio; public Node(int i,ArrayList<object> in,int l,ArrayList<object> out){ super(); this.node_in=i; if(in==null) in=new ArrayList<>(); this.inbag_object=in; this.leftv=l; this.outbag_object=out; this.prio=this.find_prio(); } private int find_prio() { // TODO Auto-generated method stub int bag_left=this.leftv; int p=this.get_bag_value(); int i=this.node_in; object iobject=null; while(true){ if(i>=this.inbag_object.size()) break; iobject=this.inbag_object.get(i); if(iobject.getweight()>bag_left) break; bag_left-=iobject.getweight(); p+=iobject.getvalue();

i++; } if(i<=this.inbag_object.size()-1) p+=iobject.getvw()*bag_left; return p; } public int get_bag_weight(){ int w=0; for(object o:this.inbag_object){ w+=o.getweight(); } return w; } public int get_bag_value(){ int w=0; for(object o:this.inbag_object){ w+=o.getvalue(); } return w; } @Override public int compareTo(Node o) { // TODO Auto-generated method stub if(this.prio>o.prio) return -1; if(this.prio<o.prio) return 1; return 0; } public boolean isend(){ if(this.node_in==this.outbag_object.size()) return true; else return false; } public ArrayList<object> get_in_bag_object(){ return this.inbag_object; } public int get_node_in(){return this.node_in;} public int get_bag_leftv(){return this.leftv;} public int get_bag_prio(){return this.prio;} public String toString(){ return "node in"+this.node_in+"node prio"+this.prio; } } -----------------------------------------------------------------------

package bag01b; public class object implements Comparable<object>{ private static int ids=1; private int id; private int weihgt; private int value; public object(int w,int v){ super(); this.weihgt=w; this.value=v; this.id=ids++; } public int getid(){return this.id;} public int getweight(){return this.weihgt;} public int getvalue(){return this.value;} public float getvw(){return (float)this.value/this.weihgt;} @Override public int compareTo(object o) { // TODO Auto-generated method stub if(this.getvw()>o.getvw()) return -1; if(this.getvw()<o.getvw()) return 1; return 0; } public String toString(){ return "object "+this.id+" } }

";

01背包问题实验报告
01背包问题实验报告 - 算法设计与分析 实验报告书 实验名称: 0/1 背包问题 学 号: 姓 名: 实验时间: 2015 年 6 月 1 日 《算法分析与设计》实...

0-1背包问题的算法设计策略对比与讲解
0-1背包问题算法设计策略对比与讲解 - 算法设计与分析大作业 班姓学 级: 名: 号: 电子 154 吴志勇 1049731503279 李瑞芳 2015.12.25 任课老师:...