回溯法、分支限界法解0-1背包問題(計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告)

1、實(shí)驗(yàn)報(bào)告課程名稱： 算法設(shè)計(jì)與分析 實(shí)驗(yàn)名稱：回溯法、分支限界法解0-1背包問題 任課教師：張錦雄 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)班 級：2007 級1班 學(xué) 號：姓 名：藍(lán)冠恒 完成日期： 2011 年1月12日、實(shí)驗(yàn)?zāi)康模赫莆栈厮莘?、分支限界法的原理，并能夠按其原理編程?shí)現(xiàn)解決0-1背包問題，以加深對回溯法、分支限界法的理解。二、主要實(shí)驗(yàn)內(nèi)容及要求：1 要求分別用回溯法和分支限界法求解0-1背包問題；2 要求交互輸入背包容量，物品重量數(shù)組，物品價(jià)值數(shù)組；3.要求顯示結(jié)果。三、實(shí)驗(yàn)環(huán)境和工具：操作系統(tǒng):win7操作系統(tǒng)開發(fā)工具：eclipse34 jdk1.6開發(fā)語言：java四、實(shí)驗(yàn)結(jié)果與結(jié)論

2、：（經(jīng)調(diào)試正確的源程序和程序的運(yùn)行結(jié)果）1.1、回溯法求解0-1背包問題源代碼：package cn.l gh;import java.io.BufferedReader;import java.i o.ln putStreamReader;import java.util.Arrays;import java.util.Comparator;/*回溯法解0-1背包問題。* author 藍(lán)冠恒*/public class BTKn apsack double c; / 背包重量int n; / 物品總數(shù)double w; / 物品重量數(shù)組double p; / 物品價(jià)值數(shù)組doublecw;

3、/當(dāng)前重量doublecp ;/當(dāng)前價(jià)值doublebestp ;/ 當(dāng)前最優(yōu)價(jià)值/*回溯法解0- 1背包問題。*parampp*物品價(jià)值數(shù)組*paramww*物品重量數(shù)組*paramcc*背包重量*return最優(yōu)價(jià)值*/public doublekn apsack(double pp, double ww, double cc) c = cc;n = pp.len gth;cw = 0.0;cp = 0.0;bestp = 0.0;Eleme nt q =new Eleme nt n;for ( int i = 0; i <n; i+) qi = new Eleme nt(i + 1

4、, ppi / wwi);Arrays. sort (q, new ElemComparator();p = new double n + 1;w = new double n + 1;for ( int i = 1; i <=n; i+) pi = ppqi - 1.id - 1;wi = wwqi - 1.id - 1;backtrack(1);return bestp ;/回溯過程private void backtrack( int i) if (i > n) / 達(dá)到葉節(jié)點(diǎn)bestp = cp;return ;if ( cw + wi <= c) cw +=wi;c

5、p +=pi；backtrack(1 + i);cw -=wi;cp -=pi；if (bound(i + 1) >bestp ) backtrack(1 + i);/計(jì)算上界值private double bou nd( int i) double cleft = c - cw;doublebound = cp ;/以物品單位重量價(jià)值遞減順序裝入物品while (i <= n && wi <= cleft) cleft -=wi;bou nd +=pi;i+;/裝滿背包if (i <= n) bou nd += pi * cleft /wi;retur

6、 nbou nd;*物體編號和單位重量價(jià)值載體。* author 藍(lán)冠恒*/publicclassEleme nt intid ; / 編號double d; /單位重量價(jià)值publicEleme nt(int id, double d) this . id = id;this . d = d;/*比較器author 藍(lán)冠恒*/ public class ElemComparator impleme nts Comparator<Object> public int compare(Object object1, Object object2) Element element1 =

7、 (Element) object1;Element element2 = (Element) object2;if (eleme nt1. d < eleme nt2.d) return 1; else return 0;public static void main( Stri ng args) String in put;Stri ng flag;double capacity = 0;double pp;double ww;double bestP=0.0;BTKn apsack btK napsack=new BTKn apsack();BufferedReader in =

8、new BufferedReader( new InputStreamReader(System.in );do try do System. out .println("請選擇數(shù)字功能鍵：1-輸入數(shù)據(jù)，2-退岀系統(tǒng)":flag = in .readL in e().trim();while (!(flag.equals("1" ) | flag.equals("2");if(flag.equals("2" ) Ibreak ; doSystem. out .println("請輸入各物品重量，數(shù)據(jù)之間必

9、須以頓號間隔分開！“in put = in. readL in e().trim();in put = in. readL in e().replaceAll("" "" ); while(input.equals("");if (input.equals("2" )break ;String datas = input.split("、");int n1 = datas. len gth ;pp= new double n 1;ww=new double n 1;for (int i = 0;

10、 i < n1; i+) wwi= Double. parseDouble (datasi);do System. out .println(”請輸入各物品價(jià)值，數(shù)據(jù)之間必須以頓號間隔分開！");in put = in. readL in e().trim();in put = in .readLi ne().replaceAll("",""); while(input.equals("");if (input.equals("2" )break ;datas= input.split("

11、、");int n2 = datas. len gth ;if (n 1!=n2)System. out .println( ”輸入數(shù)據(jù)個(gè)數(shù)不一致，重新輸入")；con ti nue;for (int i = 0; i < n1; i+) ppi= Double.parseDouble (datasi);do System. out .println("請輸入背包的容量：")；in put = in. readL in e().trim();in put = in .readLi ne().replaceAll("","

12、;"); while(input.equals("");if (input.equals("2" )break ;capacity=Double. parseDouble (in put);bestP=btK napsack.k napsack(pp, ww, capacity);System. out .println("回溯法解得最優(yōu)價(jià)值："+bestP); catch(Exception e) e.pri ntStackTrace(); while ( true );單B1.2、運(yùn)行結(jié)果:X 禺貶劇列cJ S - C3

13、<termirated> BTKnapsack Java Applkaticn E：n$tallS請輸入各物品重量，數(shù)據(jù)之間必須以頓號間隔分開!請選擇數(shù)字功能鍵：】一輸入數(shù)擔(dān)，"退岀系統(tǒng)請輸入各物品重量，數(shù)據(jù)之間必須以頓號間隔分開!2.1、分支限界法求解0-1背包問題源代碼:Problems ® Javadocpackage import import import器蠶務(wù)緇if；二訣數(shù)瘞2退出系統(tǒng)cn .Igh; java.io.BufferedReader; java.i o.ln putStreamReader; java.util.Arrays;請選擇數(shù)字

14、功能鍵：1一輸入數(shù)據(jù)，2退出系統(tǒng)/*分支界限法解0- 1背包問題。* author 藍(lán)冠恒loo y 120 x eo 請輸入背包的容量:50、40 x IS x 2S > 10請輸入各物品價(jià)值，數(shù)振之間必須以頓號間隔分幵!250 x 80 > 45 > 100 > 20請輸入背包的W1：2032 x 10 > 18請輸入各物品價(jià)值，數(shù)擔(dān)之間必須以頓號間隔分開!B0回洌法解得最優(yōu)恰值：35.0 請選擇數(shù)字功能鍵：1輸入數(shù)據(jù)，2退出系統(tǒng)|J BTKrrap sack Java S3=臣 Outline 克nackaae cn,lah:鳧Q疋0 P 亠一 “”、彳l&

15、#187;L.Declaration 貝 Console S3 '*/public classBBK napsack double c; /背包重量int n; / 物品總數(shù)doublew;/物品重量數(shù)組doublep;/物品價(jià)值數(shù)組doublecw;/當(dāng)前重量doublecp ;/當(dāng)前價(jià)值int bestxJ/最優(yōu)解MaxHeap maxHeap = new MaxHeap(); /活節(jié)點(diǎn)優(yōu)先隊(duì)列/計(jì)算節(jié)點(diǎn)所對應(yīng)的節(jié)點(diǎn)的上界private double bou nd( int i) double cleft = c - cw;double b = cp ;/以物品單位重量價(jià)值遞減裝填

16、剩余容量while (i <= n && wi <= cleft) cleft -=wi;b +=pi;i+;/裝填剩余容量裝滿背包if (i <= n) b += pi / wi * cleft;return b;/添加新的活節(jié)點(diǎn)到子集樹和優(yōu)先隊(duì)列中private void addLiveNode( double upperProfit,double pp, double ww,int level, BBnode pare nt,boolea nleftChild) BB node b =new BB node(pare nt, leftChild);Hea

17、pNode node = new HeapNode(b, upperProfit, pp, ww, level); maxHeap .put(node);/優(yōu)先隊(duì)列式分支界限法private doublebbK napsack() BBnode enode = n ull ;int i = 1;double bestp = 0.0;double up = bou nd(1);while (i != n + 1) double wt = cw +wi;/檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的左兒子節(jié)點(diǎn)if (wt <= c) if ( cp + pi > bestp) bestp = cp +pi;ad

18、dLiveNode(up,cp + pi, cw + wi, i + 1, eno de,true );up = bou nd(i + 1);/檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的右兒子節(jié)點(diǎn)if (up >= bestp) addLiveNode(up, cp , cw, i + 1, eno de,false );HeapNode node = maxHeap .removeMax();enode = no de. liveNode ;cw = no de.weight ;cp = no fit;up = no de.upperProfit ;i = no de.level ;/構(gòu)造當(dāng)前最優(yōu)

19、解for ( int j = n; j > 0; j-) bestx j = (eno de.leftChild ) ? 1 : 0;enode = eno de.pare nt;return cp;*將個(gè)物體依其單位重量價(jià)值從大到小排列，然后調(diào)用bbKnapsack完成對子集樹優(yōu)先隊(duì)列式分支界*限搜索。* return 最優(yōu)解*/public double knapsack(double pp, double ww, double cc, int xx) c = cc;n = pp. len gth ;Eleme nt q =new Eleme ntn;double ws = 0.0;

20、double ps = 0.0;for ( int i = 0; i <n; i+) qi = new Eleme nt(i + 1, ppi / wwi); ps += ppi;ws += wwi;if (ws <= c) for ( int i = 1; i <=n; i+) xxi = 1;return ps;/依單位重量價(jià)值排序Arrays. sort (q,newElemComparator();p =new double n + '1;w =new double n + '1;for(int i = 1; i <=n; i+) pi = pp

21、qi - 1.id - 1;wi = wwqi - 1.id - 1;cw = 0.0;cp = 0.0;bestx = new int n + 1; maxHeap = new MaxHeap();/ 調(diào)用bbKnapsack 求問題的最優(yōu)解 double maxp = bbK napsack();for (int i = 1; i <=n; i+) xxqi - 1.id - 1 = bestx i;return maxp;public static void main( Stri ng arg) String in put;Stri ng flag;double capacity

22、= 0;double pp;double ww;int xx;double bestP=0.0;BBK napsack bbK napsack=new BBK napsack();BufferedReader do in = new BufferedReader(new InputStreamReader(System.in )；trydo System. out .println( flag = in .readL in e().trim(); while (!(flag.equals("請選擇數(shù)字功能鍵:"1" ) | flag.equals(1-輸入數(shù)據(jù)，2

23、-退岀系統(tǒng)“);"2");if (flag.equals( break ;do "2" ) System. out .println("請輸入各物品重量,數(shù)據(jù)之間必須以頓號間隔分開!);in put = in .readLi ne().trim();in put = in .readLi ne().replaceAll(I! I!III!); while (input.equals("");if (input.equals("2" )breakString datas = input.split(&quo

24、t;、");int n1 = datas. len gth ;pp= new double n 1;ww=new double n 1;for (int i = 0; i < n1; i+) wwi= Double. parseDouble (datasi);do System. out .println("請輸入各物品價(jià)值,數(shù)據(jù)之間必須以頓號間隔分開!);in put = in .readLi ne().trim();in put = in .readLi ne().replaceAll(I! I!III!); while (input.equals("&

25、quot;);if (input.equals("2" )break ;datas= input.split("、");int n2 = datas.len gth;if (n 1!=n2)System. out .println("輸入數(shù)據(jù)個(gè)數(shù)不一致，重新輸入");con ti nue;for (int i = 0; i < n1; i+) ppi= Double.parseDouble (datasi);do System. out .println("請輸入背包的容量：")；in put = in. r

26、eadL in e().trim();in put = in .readLi ne().replaceAll("",""); while (input.equals("");if (input.equals("2" )break ;xx= new int n 1;capacity=Double. parseDouble (in put);bestP=bbK napsack.k napsack(pp, ww, capacity, xx);System. out .println( "分支界限法法解得最優(yōu)價(jià)值

27、："+bestP);System. out .println( "各個(gè)被裝入物品情況(1表示被裝入，0表示未被裝入)：");for (int i = 0; i < n1; i+) System. out .print(xxi+"");System. out .println( "n"); catch (Exception e) e.pri ntStackTrace(); while ( true );packagecn.l gh;/*分支界限節(jié)點(diǎn)* author 藍(lán)冠恒*/public class BBnode BBn

28、ode parent ; / 父節(jié)點(diǎn)booleanleftChild ; / 左孩子標(biāo)識publicBBn ode( BBnode pare nt,boolea nleftChild) this . pare nt=pare nt;this . leftChild =leftChild;packagecn.l gh;import java.util.Comparator;/* Eleme nt 對象比較器* author 藍(lán)冠恒*/public class ElemComparator impleme nts Comparator<Object>public int compare

29、(Object objects Object object2) Eleme nt eleme nt1 = (Eleme nt)object1;Eleme nt eleme nt2 = (Eleme nt)object2;if (eleme nt1.d < eleme nt2.d) return 1; else return 0;package cn.l gh;/*物品編號和單位重量價(jià)值載體。* author 藍(lán)冠恒*/public class Eleme nt int id ; /物品編號double d; /單位重量價(jià)值publicEleme nt(int id, double d)

30、this . id =id;this . d=d;package cn.l gh;import java.util.Comparator;/*堆節(jié)點(diǎn)比較器。* author 藍(lán)冠恒*/public class HeapComparatorimpleme ntsComparator<Object>public int compare(Object objectl, Object object2) HeapNode heapNodel = (HeapNode)objectl;HeapNode heapNode2 = (HeapNode)object2;if (heapNode1. up

31、perProfit < heapNode2. upperProfit ) return 1; else return 0;package cn.l gh;/*堆節(jié)點(diǎn)* author 藍(lán)冠恒*/public class HeapNode BBn ode liveNode;/活節(jié)點(diǎn)doubleupperProfit;/節(jié)點(diǎn)價(jià)值上限doubleprofit ;:/節(jié)點(diǎn)所對應(yīng)的價(jià)值doubleweight ;:/節(jié)點(diǎn)所對應(yīng)的重量int level ; /活節(jié)點(diǎn)在子集樹中所處的層次序/構(gòu)造方法publicHeapNode(BB node liveNode,double upperProfit,do

32、uble profit,double weight, int level) this . liveNode = liveNode;this . upperProfit = upperProfit;this . profit = profit;this . weight = weight;this . level = level;import java.util.List;/*裝載和管理HeapNode對象。* author 藍(lán)冠恒*/public class MaxHeap /堆節(jié)點(diǎn)容器private List<HeapNode> heap =new ArrayList<HeapNode>(); public void put(HeapNode heapNode)he