回溯法、分支限界法解0-1背包問題(就設(shè)計(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ù) 班 級(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