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

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

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

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

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

5、價(jià)值排序，從大 到小取即可。 當(dāng)一件背包物品不可分割的時(shí)候，(因?yàn)椴豢煞指睿跃退惆?物品的單位體積的價(jià)值大的先取也不一定是最優(yōu)解)此時(shí)使用貪心是不對(duì)的，應(yīng) 使用動(dòng)態(tài)規(guī)劃。設(shè)計(jì)方法時(shí)間復(fù)雜度優(yōu)點(diǎn)缺點(diǎn)動(dòng)態(tài)規(guī)劃Minnc，2n可求得最優(yōu)決策序列速度慢貪心方法0(2n)速度較快很難得到最優(yōu)解回溯法O (n2n)能夠得到最優(yōu)解時(shí)間復(fù)雜度較咼分支限界法O(2n)速度較快，易求解占用內(nèi)存大，效率不咼5需要提交不同算法的實(shí)現(xiàn)代碼和總結(jié)報(bào)告動(dòng)態(tài)規(guī)劃方法：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;/ 按單位重量?jī)r(jià)值 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;/ 排序后的重量和價(jià)值分別存到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;/ 包內(nèi)現(xiàn)存貨品的重量int value=0;/ 包內(nèi)現(xiàn)存貨品總價(jià)值for (int i = 0; i n;i+)if(s + w1 i weight)value += v1 i;s += w1 i;背包中物品的最大總價(jià)值為” + 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;/按單位重量?jī)r(jià)值

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;/ 排序后的重量和價(jià)值分別存到 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背包中物品的最大總價(jià)值為” + 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