-動(dòng)態(tài)規(guī)劃解決算法0-1背包問題實(shí)驗(yàn)報(bào)告(含源代碼)

1、 3/3動(dòng)態(tài)規(guī)劃解決算法0-1背包問題實(shí)驗(yàn)報(bào)告(含源代碼) 西安郵電大學(xué) （計(jì)算機(jī)學(xué)院） 課內(nèi)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)名稱：動(dòng)態(tài)規(guī)劃 專業(yè)名稱：計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí)： 學(xué)生姓名： 學(xué)號(hào)（8位）： 指導(dǎo)教師： 實(shí)驗(yàn)日期：2014年5月9日 一實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境 1.使用動(dòng)態(tài)規(guī)劃法和回溯法生成兩個(gè)長(zhǎng)字符串的最優(yōu)化比對(duì)結(jié)果通過實(shí)際案例，領(lǐng)會(huì)算法的執(zhí)行效率。 2.掌握動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法的原理，并能夠按其原理編程實(shí)現(xiàn)解決0-1背包問題，以加深對(duì)上述方法的理解。 實(shí)驗(yàn)環(huán)境：Visual C+ 6.0 二. 實(shí)驗(yàn)內(nèi)容 1.設(shè)計(jì)一個(gè)O（n2）時(shí)間的算法，找出由n個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào)遞增子序列

2、2.將算法分析題31中算法的計(jì)算時(shí)間減至O（nlogn） 3.給定n種物品和一個(gè)背包。物品i的重量是，其價(jià)值為，背包容量為C。問應(yīng)該如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？ 三方案設(shè)計(jì) 1. 動(dòng)態(tài)規(guī)劃的一個(gè)計(jì)算兩個(gè)序列的最長(zhǎng)公共子序列的方法如下： 以兩個(gè)序列X、Y 為例子： 設(shè)有二維數(shù)組fi,j 表示X 的i 位和Y 的j 位之前的最長(zhǎng)公共子序列的長(zhǎng)度，則有： f11 = same(1,1); fi,j = maxfi-1j -1 + same(i,j),fi-1,j,fi,j-1 其中，same(a,b)當(dāng)X 的第 a 位與Y 的第 b 位相同時(shí)為“1”，否則為“0”。 此時(shí)

3、，二維數(shù)組中最大的數(shù)便是X 和Y 的最長(zhǎng)公共子序列的長(zhǎng)度，依據(jù)該數(shù)組回溯，便可找出最長(zhǎng)公共子序列。 該算法的空間、時(shí)間復(fù)雜度均為O(n2)，經(jīng)過優(yōu)化后，空間復(fù)雜度可為O(n)。 核心代碼： void LCSL(int m,int n,int *x,int *y,int cN,int bN) c00=0; int i,j; for(i=1;i=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; cout m(n,j)= 0 0n k w #include int V200200;/前i 個(gè)物品裝入容量為j 的背包中獲得的最大價(jià)值 int max(int

4、 a,int b) if(a=b) return a; else return b; int KnapSack(int n,int w,int v,int x,int C) int i,j; for(i=0;i=0;i-) if(VijVi-1j) xi=1; j=j-wi; else xi=0; printf(選中的物品是:n); for(i=0;in;i+) printf(%d ,xi); printf(n); return Vn-1C; void main() int s;/獲得的最大價(jià)值 int w15;/物品的重量 int v15;/物品的價(jià)值 int x15;/物品的選取狀態(tài) in

5、t n,i; int C;/背包最大容量 n=5; printf(請(qǐng)輸入背包的最大容量:n); scanf(%d, printf(輸入物品數(shù):n); scanf(%d, printf(請(qǐng)分別輸入物品的重量:n); for(i=0;in;i+) scanf(%d, printf(請(qǐng)分別輸入物品的價(jià)值:n); for(i=0;in;i+) scanf(%d, s=KnapSack(n,w,v,x,C); printf(最大物品價(jià)值為:n); printf(%dn,s); 四運(yùn)行結(jié)果 1. 2. 3. 五心得體會(huì) 通過這次實(shí)驗(yàn)，對(duì)動(dòng)態(tài)規(guī)劃法求最長(zhǎng)公共子序列有更深的理解。其實(shí)無非就是抓住書上的遞推公式進(jìn)行寫，動(dòng)態(tài)規(guī)劃依賴于上一個(gè)或者上一行的解，就是在輸出子序列的時(shí)候有問題。自己對(duì)動(dòng)態(tài)規(guī)劃、貪心、回溯法、分支限界法的原理不是非常的理解，花了很多時(shí)間看了課本上的相關(guān)內(nèi)容。同時(shí)課本所提供的代碼也是不能直接翻譯過來用，當(dāng)懂得算法的基本原理后，會(huì)發(fā)現(xiàn)數(shù)組下標(biāo)會(huì)出錯(cuò)，所以在參考課本所