01背包問題不同算法設(shè)計(jì)分析與對比

1、實(shí)驗(yàn)三 01背包問題不同算法設(shè)計(jì)、分析與對比一問題描述給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為c。問題：應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。說明：在選擇裝入背包的物品時，對每種物品i只有兩個選擇，裝入背包或不裝入背包，也不能將物品裝入背包多次。二實(shí)驗(yàn)內(nèi)容與要求實(shí)驗(yàn)內(nèi)容：1. 分析該問題適合采用哪些算法求解（包括近似解）。 動態(tài)規(guī)劃、貪心、回溯和分支限界算法。2. 分別給出不同算法求解該問題的思想與算法設(shè)計(jì)，并進(jìn)行算法復(fù)雜性分析。動態(tài)規(guī)劃：遞推方程：m(i,j) = maxm(i-1,j),m(i-1,j-wi)+vi j >= wi;

2、m(i-1,j) j < wi; 時間復(fù)雜度為O(n).貪心法： 算法思想：貪心原則為單位價值最大且重量最小，不超過背包最大承重量為約束條件。也就是說，存在單位重量價值相等的兩個包，則選取重量較小的那個背包。但是，貪心法當(dāng)在只有在解決物品可以分割的背包問題時是正確的。貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。 用貪心法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，根據(jù)某個優(yōu)化測度（可能是目標(biāo)函數(shù)，也可能不是目標(biāo)函數(shù)），每一步上都要保證能獲得局部最優(yōu)解。每一步只考慮一個數(shù)據(jù)，它的選取應(yīng)滿足局部優(yōu)化條件。若下一個數(shù)據(jù)與部分最優(yōu)解

3、連在一起不再是可行解時，就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加為止。回溯法： 回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。這種具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。 對于有n種可選物品的0/1背包問題，其解空間由長度為n的0-1向量組成,可用子集數(shù)表示。在搜索解空間樹時，只要其左兒子結(jié)點(diǎn)是一個可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時就進(jìn)入右子樹搜索。時間復(fù)雜度為：O(2n)空間復(fù)雜度為：O(n)分支限界算法： 首先，要對輸入

4、數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量價值從大到小進(jìn)行排列。在優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。     算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時為問題的最優(yōu)值。3. 設(shè)計(jì)并實(shí)現(xiàn)所設(shè)計(jì)的算法。4. 對比不同算法求解該問題的優(yōu)劣。 這動態(tài)規(guī)劃算法和貪心算法是用來分別解決不同類型的背包問題的，當(dāng)一件背包物品可以分

5、割的時候，使用貪心算法，按物品的單位體積的價值排序，從大到小取即可。 當(dāng)一件背包物品不可分割的時候，（因?yàn)椴豢煞指?，所以就算按物品的單位體積的價值大的先取也不一定是最優(yōu)解）此時使用貪心是不對的，應(yīng)使用動態(tài)規(guī)劃。 設(shè)計(jì)方法時間復(fù)雜度優(yōu)點(diǎn)缺點(diǎn)動態(tài)規(guī)劃Minnc，2n可求得最優(yōu)決策序列速度慢貪心方法O（2n）速度較快很難得到最優(yōu)解回溯法O（n2n）能夠得到最優(yōu)解時間復(fù)雜度較高分支限界法O（2n）速度較快，易求解占用內(nèi)存大，效率不高5.需要提交不同算法的實(shí)現(xiàn)代碼和總結(jié)報(bào)告。動態(tài)規(guī)劃方法：public class Knapsack public static void main(String args)

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

7、< value.length; i+) vi = valuei;wi = weighi;for (int i = 1; i < value.length; i+) for (int k = 1; k <= weight; k+) if (wi <= k) cik = max(ci - 1k, ci - 1k - wi + vi); else cik = ci - 1k;System.out.println(cvalue.length - 1weight);private static int max(int i, int j) int k = i > j ? i

8、: 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 doublen; int index = new i

9、ntn; 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; indexj = x; /排序后的重量和價值分別存到w1和v1中 int w1 = new intn;

10、 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;/包內(nèi)現(xiàn)存貨品的重量 int value=0;/包內(nèi)現(xiàn)存貨品總價值 for(int i = 0; i < n;i+) if(s + w1i < weight) value += v1i; s += w1i; System.out.println(&quo

11、t;背包中物品的最大總價值為" + 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

12、n; 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; indexj = x; /排序后的重量和價值分別存到w1和v1

13、中 int w1 = new intn; int v1 = new intn; for(int i = 0;i < n;i+) w1i = windexi; v1i = vindexi; /調(diào)用函數(shù)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

14、;int maxValue = 0;int i = 0;int n = v1.length;while(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;public

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

16、;import java.util.ArrayList;import java.util.Collections;import java.util.PriorityQueue;public class bag private int bagv; private ArrayList<object> objects; private int maxvalue; private ArrayList<object> result_objects; public bag(int v,ArrayList<object> o) super(); this.bagv=v;

17、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 when maxvalue:"+this.result_objects); public void findmaxvalue() PriorityQueue<Node> enod

18、e=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

19、_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

20、(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.obj

21、ects); 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;privat

22、e 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 stubint bag_

23、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+=

24、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;Overridepublic int compareTo(Node o) / TODO Auto-generated method stubif(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;elsereturn false;public ArrayList<object> get_in_bag_object()return this.inbag_object;public int get_node_i