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

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-1

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

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

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

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

6、 100, 120 ;in t 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 ;int w = new int ;int c = new int weight + 1;int d = new int 100;for (int i = 0; i ; i+) vi = valuei;wi = weigh i;for (int i = 1; i

7、; i+) for (int k = 1; k = weight; k+) if (wi j i : j;return k;贪心法：public class GreedyKnapSack public static void main(String args) in t value = 0, 60, 100, 120 ;in t weigh = 0, 10, 20, 30 ;int weight = 50;Knapsack1 (weight, value, weigh );private static void Knapsack1(int weight, int v, int w) int n

8、 =;double r = new double n;int index = new int n;for(int i = 0;i n; i+)ri = (double )vi / (double )wi;in dex i = 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 = index j;index j = x;/ 排序后的重量和价值分别存到w1

9、 和 v1 中int w1 = new intn;int v1 = new intn;for (int i = 0;i n;i+)w1i = w index i;v1i = vindex i;(w1);(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;背包中物品的最大总价值为” + value);回溯法：public class BacktrackKnapSack public static void main(Stri

10、ng args) in t value = 0, 60, 100, 120 ;in t weigh = 0, 10, 20, 30 ;int weight = 50;Knapsack1 (weight, value, weigh );private static void Knapsack1(int weight, int v, int w) int n =;double r = new double n;int index = new int n;for(int i = 0;i n; i+)ri = (double )vi / (double )wi;in dexi = i;/按单位重量价值

11、 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 = index j;index j = x;/ 排序后的重量和价值分别存到 w1 和 v1 中int w1 = new intn;int v1 = new intn;for (int i = 0;i = 0)if(CurrentWeight + w1i weight)Curre ntWeight += w1 i;Curre

12、 ntValue += v1 i;i+;elsebreak;if(i n)maxValue = CurrentValue ;1背包中物品的最大总价值为” + maxValue);分支限界算法：package bagO1b;import class bag01do public static void main(String args) / TODO Auto-ge nerated method stubArrayList objects = new ArrayList();(new object(10,60);(new object(20,100);bag b=new bag(50,objec

13、ts );();();package bag01b;importclass bag private int bagv;private ArrayList objects ;private int maxvalue ;private ArrayList result_objects ;public bag(int v,ArrayList o) super ();=v;=o;=0;=null ;(objects);public void show()maxvalue :+ ;the object when maxvalue: +;public void findmaxvalue()Priority

14、Queue enode= new PriorityQueue();Node node= new Node(0,null ,bagv,;(node);while (true )if()break ;node=();if()=();=new ArrayList();return ;int i=();object iobject=if ()+()=ArrayList newnodeinbag= new ArrayList();(iobject);int newnodebagv=()();Node newnode= new Node(i+1,newnodeinbag,newnodebagv,;(new

15、node);if ()=();=new ArrayList();Node newnode= new Node(i+1,(),(),;if()(newnode);package bag01b;import class Node implements Comparableprivate 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,Array

16、List out) super();=i;if (in=null )in= new ArrayList();=in;=l;=out;=();private int find_prio() / TODO Auto-generated method stubint bag_left=;int p=();int i=;object iobject= null;while (true )if (i=break;iobject= if ()bag_left) break;bag_left-=();p+=();i+;if (i return -1;if return 1;return 0;public b

17、oolean isend()if= return true;elsereturn false;public ArrayList get_in_bag_object() return ;public int get_node_in() return ;public int get_bag_leftv() return ;public int get_bag_prio() return ;public String toString()return node in +node prio +;package bag01b;public class object implements Comparable private static int ids=1;private int id;private int weihgt ;private int value; public object( int w,int v) super();=w;=v;=ids+;public