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

1、实验三 01背包问题不同算法设计、分析与对比一问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问题：应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。说明：在选择装入背包的物品时，对每种物品i只有两个选择，装入背包或不装入背包，也不能将物品装入背包多次。二实验内容与要求实验内容：1. 分析该问题适合采用哪些算法求解（包括近似解）。 动态规划、贪心、回溯和分支限界算法。2. 分别给出不同算法求解该问题的思想与算法设计，并进行算法复杂性分析。动态规划：递推方程：m(i,j) = maxm(i-1,j),m(i-1,j-wi)+vi j = wi; m(i-

2、1,j) j wi; 时间复杂度为O(n).贪心法： 算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。但是，贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 用贪心法设计算法的特点是一步一步地进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行

3、解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。回溯法： 回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。 对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。时间复杂度为：O(2n)空间复杂度为：O(n)分支限界算法： 首先，要对输入数据进行预处理，将

4、各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。3. 设计并实现所设计的算法。4. 对比不同算法求解该问题的优劣。 这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的，当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大

5、到小取即可。 当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。 设计方法时间复杂度优点缺点动态规划Minnc，2n可求得最优决策序列速度慢贪心方法O（2n）速度较快很难得到最优解回溯法O（n2n）能够得到最优解时间复杂度较高分支限界法O（2n）速度较快，易求解占用内存大，效率不高5.需要提交不同算法的实现代码和总结报告。动态规划方法：public class Knapsack public static void main(String args) int value = 0, 60, 100, 120

6、 ;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 intvalue.length;int w = new intweigh.length;int c = new intvalue.lengthweight + 1;int d = new int 100;for (int i = 0; i value.length; i+) vi = value

7、i;wi = weighi;for (int i = 1; i value.length; i+) for (int k = 1; k = weight; k+) if (wi 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

8、 Knapsack1(int weight, int v, int w) int n = v.length;double r = new doublen; int index = new intn; for(int i = 0;i n; i+) ri = (double)vi / (double)wi; indexi = i; /按单位重量价值ri=vi/wi降序排列 double temp = 0;for(int i = 0;i n-1;i+) for(int j = i+1;j n;j+) if(ri rj) temp = ri; ri = rj; rj = temp; int x = i

9、ndexi; indexi = indexj; indexj = x; /排序后的重量和价值分别存到w1和v1中 int w1 = new intn; int v1 = new intn; for(int i = 0;i n;i+) w1i = windexi; v1i = vindexi; 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 +

10、 w1i weight) value += v1i; s += w1i; 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

11、v, int w) int n = v.length;double r = new doublen; int index = new intn; for(int i = 0;i n; i+) ri = (double)vi / (double)wi; indexi = i; /按单位重量价值ri=vi/wi降序排列 double temp = 0;for(int i = 0;i n-1;i+) for(int j = i+1;j n;j+) if(ri rj) temp = ri; ri = rj; rj = temp; int x = indexi; indexi = indexj; ind

12、exj = x; /排序后的重量和价值分别存到w1和v1中 int w1 = new intn; int v1 = new intn; for(int i = 0;i = 0)if(CurrentWeight + w1i weight)CurrentWeight += w1i;CurrentValue += v1i;i+;else break;if(i n)maxValue = CurrentValue;System.out.println(1背包中物品的最大总价值为 + maxValue);分支限界算法：package bag01b;import java.util.ArrayList;pu

13、blic class bag01do public static void main(String args) / TODO Auto-generated method stubArrayList 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.

14、ArrayList;import java.util.Collections;import java.util.PriorityQueue;public class bag private int bagv; private ArrayList objects; private int maxvalue; private ArrayList result_objects; public bag(int v,ArrayList o) super(); this.bagv=v; this.objects=o; this.maxvalue=0; this.result_objects=null; C

15、ollections.sort(objects); public void show() System.out.println(maxvalue :+ this.maxvalue); System.out.println(the object when maxvalue:+this.result_objects); public void findmaxvalue() PriorityQueue enode=new PriorityQueue(); Node node=new Node(0,null,bagv,this.objects); enode.offer(node); while(tr

16、ue) 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 new

17、nodeinbag=new ArrayList(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();

18、 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 Comparableprivate

19、 int node_in;private ArrayList inbag_object;private ArrayList outbag_object;private int leftv;private int prio;public Node(int i,ArrayList in,int l,ArrayList 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();p

20、rivate int find_prio() / TODO Auto-generated method stubint 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+=iobje

21、ct.getvalue();i+;if(io.prio) return -1;if(this.prioo.prio) return 1;return 0;public boolean isend()if(this.node_in=this.outbag_object.size()return true;elsereturn false;public ArrayList get_in_bag_object()return this.inbag_object;public int get_node_in()return this.node_in;public int get_bag_leftv()return th