回溯法、分支限界法解0-1背包問題(就設(shè)計(jì)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告)_第1頁
回溯法、分支限界法解0-1背包問題(就設(shè)計(jì)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告)_第2頁
回溯法、分支限界法解0-1背包問題(就設(shè)計(jì)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告)_第3頁
回溯法、分支限界法解0-1背包問題(就設(shè)計(jì)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告)_第4頁
回溯法、分支限界法解0-1背包問題(就設(shè)計(jì)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告)_第5頁
已閱讀5頁,還剩10頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、實(shí) 驗(yàn) 報(bào) 告 課程名稱: 算法設(shè)計(jì)與分析 實(shí)驗(yàn)名稱:回溯法、分支限界法解0-1背包問題任課教師: 張錦雄 專 業(yè): 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí): 2007 級(jí) 1班 學(xué) 號(hào): 姓 名: 藍(lán)冠恒 完成日期: 2011年1月12日 一、實(shí)驗(yàn)?zāi)康模赫莆栈厮莘?、分支限界法的原理,并能夠按其原理編程?shí)現(xiàn)解決0-1背包問題,以加深對(duì)回溯法、分支限界法的理解。 二、主要實(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ā)工具:eclipse3.4、jdk1.6開發(fā)語言:

2、java四、實(shí)驗(yàn)結(jié)果與結(jié)論:(經(jīng)調(diào)試正確的源程序和程序的運(yùn)行結(jié)果)1.1、回溯法求解0-1背包問題源代碼: package cn.lgh;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Comparator;/* * 回溯法解0-1背包問題。 * author 藍(lán)冠恒 */public class BTKnapsack double c;/ 背包重量 int n; / 物品總數(shù) double w;/ 物品重量數(shù)組 double p;/

3、物品價(jià)值數(shù)組 double cw; / 當(dāng)前重量 double cp; / 當(dāng)前價(jià)值 double bestp; / 當(dāng)前最優(yōu)價(jià)值/* * 回溯法解0-1背包問題。 * param pp * 物品價(jià)值數(shù)組 * param ww * 物品重量數(shù)組 * param cc * 背包重量 * return 最優(yōu)價(jià)值 */public double knapsack(double pp, double ww, double cc) c = cc;n = pp.length;cw = 0.0;cp = 0.0;bestp = 0.0;Element q = new Elementn;for (int i

4、= 0; i < n; i+) qi = new Element(i + 1, ppi / wwi);Arrays.sort(q, new ElemComparator();p = new doublen + 1;w = new doublen + 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;ret

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

6、 <= n) bound += pi * cleft / wi;return bound;/* * 物體編號(hào)和單位重量?jī)r(jià)值載體。 * author 藍(lán)冠恒 */public class Element int id;/ 編號(hào)double d;/ 單位重量?jī)r(jià)值public Element(int id, double d) this.id = id;this.d = d;/* * 比較器 * author 藍(lán)冠恒 */public class ElemComparator implements Comparator<Object> public int compare(Obje

7、ct object1, Object object2) Element element1 = (Element) object1;Element element2 = (Element) object2;if (element1.d < element2.d) return 1; else return 0;public static void main(String args) String input;String flag;double capacity = 0;double pp;double ww;double bestP=0.0;BTKnapsack btKnapsack=n

8、ew BTKnapsack();BufferedReader in = new BufferedReader(new InputStreamReader(System.in);do try do System.out.println("請(qǐng)選擇數(shù)字功能鍵: 1-輸入數(shù)據(jù),2-退出系統(tǒng)");flag = in.readLine().trim(); while (!(flag.equals("1") | flag.equals("2");if (flag.equals("2") break;do System.out.p

9、rintln("請(qǐng)輸入各物品重量,數(shù)據(jù)之間必須以頓號(hào)間隔分開!");input = in.readLine().trim();input = in.readLine().replaceAll(" ", ""); while (input.equals("");if(input.equals("2")break;String datas = input.split("、");int n1 = datas.length;pp=new doublen1;ww=new doublen

10、1;for (int i = 0; i < n1; i+) wwi= Double.parseDouble(datasi);do System.out.println("請(qǐng)輸入各物品價(jià)值,數(shù)據(jù)之間必須以頓號(hào)間隔分開!");input = in.readLine().trim();input = in.readLine().replaceAll(" ", ""); while (input.equals("");if(input.equals("2")break;datas= input.s

11、plit("、");int n2 = datas.length;if(n1!=n2)System.out.println("輸入數(shù)據(jù)個(gè)數(shù)不一致,重新輸入");continue;for (int i = 0; i < n1; i+) ppi= Double.parseDouble(datasi);do System.out.println("請(qǐng)輸入背包的容量:");input = in.readLine().trim();input = in.readLine().replaceAll(" ", "&

12、quot;); while (input.equals("");if(input.equals("2")break;capacity=Double.parseDouble(input);bestP=btKnapsack.knapsack(pp, ww, capacity);System.out.println("回溯法解得最優(yōu)價(jià)值:"+bestP); catch (Exception e) e.printStackTrace(); while (true);1.2、運(yùn)行結(jié)果:2.1、分支限界法求解0-1背包問題源代碼: package

13、 cn.lgh;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;/* * 分支界限法解0-1背包問題。 * author 藍(lán)冠恒 */public class BBKnapsack double c;/ 背包重量int n; / 物品總數(shù)double w;/ 物品重量數(shù)組double p;/ 物品價(jià)值數(shù)組double cw; / 當(dāng)前重量double cp; / 當(dāng)前價(jià)值int bestx; / 最優(yōu)解MaxHeap maxHeap = new MaxHeap();/

14、活節(jié)點(diǎn)優(yōu)先隊(duì)列/ 計(jì)算節(jié)點(diǎn)所對(duì)應(yīng)的節(jié)點(diǎn)的上界private double bound(int i) double cleft = c - cw;double b = cp;/ 以物品單位重量?jī)r(jià)值遞減裝填剩余容量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

15、pp, double ww,int level, BBnode parent, boolean leftChild) BBnode b = new BBnode(parent, leftChild);HeapNode node = new HeapNode(b, upperProfit, pp, ww, level);maxHeap.put(node);/ 優(yōu)先隊(duì)列式分支界限法private double bbKnapsack() BBnode enode = null;int i = 1;double bestp = 0.0;double up = bound(1);while (i !=

16、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;addLiveNode(up, cp + pi, cw + wi, i + 1, enode, true);up = bound(i + 1);/ 檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的右兒子節(jié)點(diǎn)if (up >= bestp) addLiveNode(up, cp, cw, i + 1, enode, false);HeapNode node = maxHeap.removeMax();enode = node

17、.liveNode;cw = node.weight;cp = fit;up = node.upperProfit;i = node.level;/ 構(gòu)造當(dāng)前最優(yōu)解for (int j = n; j > 0; j-) bestxj = (enode.leftChild) ? 1 : 0;enode = enode.parent;return cp;/* 將個(gè)物體依其單位重量?jī)r(jià)值從大到小排列,然后調(diào)用bbKnapsack完成對(duì)子集樹優(yōu)先隊(duì)列式分支界*限搜索。 * * return 最優(yōu)解 */public double knapsack(double pp, double

18、ww, double cc, int xx) c = cc;n = pp.length;Element q = new Elementn;double ws = 0.0;double ps = 0.0;for (int i = 0; i < n; i+) qi = new Element(i + 1, ppi / wwi);ps += ppi;ws += wwi;if (ws <= c) for (int i = 1; i <= n; i+) xxi = 1;return ps;/ 依單位重量?jī)r(jià)值排序Arrays.sort(q, new ElemComparator();p

19、= new doublen + 1;w = new doublen + 1;for (int i = 1; i <= n; i+) pi = ppqi - 1.id - 1;wi = wwqi - 1.id - 1;cw = 0.0;cp = 0.0;bestx = new intn + 1;maxHeap = new MaxHeap();/ 調(diào)用bbKnapsack求問題的最優(yōu)解double maxp = bbKnapsack();for (int i = 1; i <= n; i+) xxqi - 1.id - 1 = bestxi;return maxp;public sta

20、tic void main(String arg) String input;String flag;double capacity = 0;double pp;double ww;int xx;double bestP=0.0;BBKnapsack bbKnapsack=new BBKnapsack();BufferedReader in = new BufferedReader(new InputStreamReader(System.in);do try do System.out.println("請(qǐng)選擇數(shù)字功能鍵: 1-輸入數(shù)據(jù),2-退出系統(tǒng)");flag = i

21、n.readLine().trim(); while (!(flag.equals("1") | flag.equals("2");if (flag.equals("2") break;do System.out.println("請(qǐng)輸入各物品重量,數(shù)據(jù)之間必須以頓號(hào)間隔分開!");input = in.readLine().trim();input = in.readLine().replaceAll(" ", ""); while (input.equals("

22、");if(input.equals("2")break;String datas = input.split("、");int n1 = datas.length;pp=new doublen1;ww=new doublen1;for (int i = 0; i < n1; i+) wwi= Double.parseDouble(datasi);do System.out.println("請(qǐng)輸入各物品價(jià)值,數(shù)據(jù)之間必須以頓號(hào)間隔分開!");input = in.readLine().trim();input = i

23、n.readLine().replaceAll(" ", ""); while (input.equals("");if(input.equals("2")break;datas= input.split("、");int n2 = datas.length;if(n1!=n2)System.out.println("輸入數(shù)據(jù)個(gè)數(shù)不一致,重新輸入");continue;for (int i = 0; i < n1; i+) ppi= Double.parseDouble

24、(datasi);do System.out.println("請(qǐng)輸入背包的容量:");input = in.readLine().trim();input = in.readLine().replaceAll(" ", ""); while (input.equals("");if(input.equals("2")break;xx=new intn1;capacity=Double.parseDouble(input);bestP=bbKnapsack.knapsack(pp, ww, ca

25、pacity, xx);System.out.println("分支界限法法解得最優(yōu)價(jià)值:"+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.printStackTrace(); while (true);package cn.lgh;/* * 分

26、支界限節(jié)點(diǎn) * author 藍(lán)冠恒 */public class BBnode BBnode parent;/父節(jié)點(diǎn)boolean leftChild;/左孩子標(biāo)識(shí)public BBnode( BBnode parent,boolean leftChild) this.parent=parent;this.leftChild=leftChild;package cn.lgh;import java.util.Comparator;/* * Element對(duì)象比較器 * author 藍(lán)冠恒 */public class ElemComparator implements Comparator

27、<Object>public int compare(Object object1, Object object2) Element element1 = (Element)object1;Element element2 = (Element)object2;if (element1.d< element2.d) return 1; else return 0;package cn.lgh;/* * 物品編號(hào)和單位重量?jī)r(jià)值載體。 * author 藍(lán)冠恒 */public class Element int id;/物品編號(hào)double d;/單位重量?jī)r(jià)值public El

28、ement(int id,double d) this.id=id;this.d=d;package cn.lgh;import java.util.Comparator;/* * 堆節(jié)點(diǎn)比較器。 * author 藍(lán)冠恒 */public class HeapComparator implements Comparator<Object>public int compare(Object object1, Object object2) HeapNode heapNode1 = (HeapNode)object1;HeapNode heapNode2 = (HeapNode)ob

29、ject2;if (heapNode1.upperProfit< heapNode2.upperProfit) return 1; else return 0;package cn.lgh;/* *堆節(jié)點(diǎn)* author 藍(lán)冠恒 */public class HeapNode BBnode liveNode; / 活節(jié)點(diǎn)double upperProfit; / 節(jié)點(diǎn)價(jià)值上限double profit; / 節(jié)點(diǎn)所對(duì)應(yīng)的價(jià)值double weight; / 節(jié)點(diǎn)所對(duì)應(yīng)的重量int level; / 活節(jié)點(diǎn)在子集樹中所處的層次序號(hào)/ 構(gòu)造方法public HeapNode(BBnode li

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論