算法分析與程序設(shè)計(jì)動(dòng)態(tài)規(guī)劃及回溯法解01背包問題(共10頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上動(dòng)態(tài)規(guī)劃法、回溯法解0-1背包問題2012級(jí) 計(jì)科 龐佳奇一、 問題描述與分析1. 動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有的解。動(dòng)態(tài)規(guī)劃算法與類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來(lái)解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的

2、重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來(lái)記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。多階段決策問題中，各個(gè)階段采取的決策，一般來(lái)說是與時(shí)間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義，稱這種解決多階段決策最優(yōu)化問題的方法為動(dòng)態(tài)規(guī)劃方法。任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并不是萬(wàn)能的。適用動(dòng)態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無(wú)后效性。1.（最優(yōu)子結(jié)構(gòu)性質(zhì)） 最優(yōu)化

3、原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2.將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無(wú)法直接影響它未來(lái)的決策，而只能通過當(dāng)前的這個(gè)狀態(tài)。換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。這就是無(wú)后向性，又稱為無(wú)后效性。3.子問題的重疊性 動(dòng)態(tài)規(guī)劃將原來(lái)具有指數(shù)級(jí)時(shí)間復(fù)雜度的改進(jìn)成了具有多項(xiàng)式時(shí)間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空

4、間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。是在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2Wn，與之相對(duì)應(yīng)的價(jià)值為P1,P2Pn。求出獲得最大價(jià)值的方案。2. 回溯法（探索與回溯法）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)的點(diǎn)稱為“回溯點(diǎn)”。在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問題的解，

5、如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果該結(jié)點(diǎn)不包含問題的解，則逐層向其祖先結(jié)點(diǎn)回溯。（其實(shí)回溯法就是對(duì)隱式圖的深度優(yōu)先搜索算法）。 若用回溯法求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹都要已被搜索遍才結(jié)束。 而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束可用回溯法求解的問題P，通常要能表達(dá)為：對(duì)于已知的由n元組（x1，x2，xn）組成的一個(gè)E=（x1，x2，xn）xiSi ，i=1，2，n，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，n。我們稱E中滿足D的全部約束條

6、件的任一n元組為問題P的一個(gè)解。解問題P的最樸素的方法就是，即對(duì)E中的所有n元組逐一地檢測(cè)其是否滿足D的全部約束，若滿足，則為問題P的一個(gè)解。但顯然，其計(jì)算量是相當(dāng)大的。我們發(fā)現(xiàn)，對(duì)于許多問題，所給定的約束集D具有完備性，即i（x1，x2，xi）滿足D中僅涉及到x1，x2，xi的所有約束意味著j（j=i）元組（x1，x2，xj）一定也滿足D中僅涉及到x1，x2，xj的所有約束，i=1，2，n。換句話說，只要存在0jn-1，使得（x1，x2，xj）違反D中僅涉及到x1，x2，xj的約束之一，則以（x1，x2，xj）為前綴的任何n元組（x1，x2，xj，xj+1，xn）一定也違反D中僅涉及到x1，

7、x2，xi的一個(gè)約束，nij。因此，對(duì)于約束集D具有完備性的問題P，一旦檢測(cè)斷定某個(gè)j元組（x1，x2，xj）違反D中僅涉及x1，x2，xj的一個(gè)約束，就可以肯定，以（x1，x2，xj）為前綴的任何n元組（x1，x2，xj，xj+1，xn）都不會(huì)是問題P的解，因而就不必去搜索它們、檢測(cè)它們。回溯法正是針對(duì)這類問題，利用這類問題的上述性質(zhì)而提出來(lái)的比枚舉法效率更高的。二、 算法設(shè)計(jì)（或算法步驟）1. 這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即fiv表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是： fiv=maxfi-1v

8、,fi-1v-ci+wi 這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來(lái)的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價(jià)值為fi-1v；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-ci的背包中”，此時(shí)能獲得的最大價(jià)值就是fi-1v-ci再加上通過放入第i件物品獲得的價(jià)值wi。2. （1）分析要解決的問題，給出你的思路，可以借助圖表等輔助表達(dá)。01背包問題用

9、回溯法實(shí)現(xiàn)就是要枚舉其所有的解空間，時(shí)間復(fù)雜度為(2)nO左右。搜索的具體方法如下：對(duì)于每一個(gè)物品i，對(duì)于該物品只有選與不選2個(gè)決策，總共有n個(gè)物品，可以順序依次考慮每個(gè)物品，這樣就形成了一棵解空間樹：基本思想就是遍歷這棵樹，以枚舉所有情況，最后進(jìn)行判斷，如果重量不超過背包容量，且價(jià)值最大的話，該方案就是最后的答案。利用回溯算法寫還可以加入一些優(yōu)化，進(jìn)行剪枝，因?yàn)楹芏嗲闆r是沒有意義的，例如當(dāng)重量大于背包容量的時(shí)候，沒有必要對(duì)剩下的物品再來(lái)決策了?；蛘邔⑹Ｏ碌乃形锲范歼x取其總價(jià)值也沒有目前已經(jīng)求得的方案的價(jià)值還大的話，也是可以剪枝的。（2）分析利用你的想法解決該問題可能會(huì)有怎樣的時(shí)空復(fù)雜度。時(shí)

10、間復(fù)雜度估計(jì)：(2)nO因?yàn)槲锲分挥羞x與不選2個(gè)決策，而總共有n個(gè)物品，所以時(shí)間復(fù)雜度為(2)nO?？臻g復(fù)雜度估計(jì)：()On因?yàn)檫f歸棧最多達(dá)到n層，而且存儲(chǔ)所有物品的信息也只需要常數(shù)個(gè)一維數(shù)組，所以最終的空間復(fù)雜度為()On。三、 算法實(shí)現(xiàn)1. 動(dòng)態(tài)規(guī)劃#include#includeint c5050; int w10,v10; int x10; int n; void KNAPSACK_DP(int n,int W);void OUTPUT_SACK(int c5050,int k) ;void KNAPSACK_DP(int n,int W) int i,k;for(k=0;k=W;k+

11、) c0k=0; for(i=1;i=n;i+) ci0=0; for(k=1;k=W;k+) if(wici-1k) cik=vi+ci-1k-wi; else cik=ci-1k; else cik=ci-1k; void OUTPUT_SACK(int c5050,int k) int i;for(i=n;i=2;i-) if(cik=ci-1k) xi=0; else xi=1; k=k-wi; x1=(c1k?1:0); for(i=1;i=n;i+) printf(%4d,xi); void main() int m; int i,j,k;printf(輸入物品個(gè)數(shù):);scanf

12、(%d,&n);printf(依次輸入物品的重量:n);for(i=1;i=n;i+) scanf(%d,&wi);printf(依次輸入物品的價(jià)值:n);for(i=1;i=n;i+) scanf(%d,&vi);printf(輸入背包最大容量:n);scanf(%d,&m); for(i=1;i=m;i+) printf(%4d,i); printf(n); KNAPSACK_DP(n,m); printf(構(gòu)造最優(yōu)解過程如下:n);for(j=1;j=5;j+) for(k=1;k=m;k+) printf(%4d,cjk); printf(n); printf(最優(yōu)解為:n);OUTP

13、UT_SACK(c,m); system(pause);2. 回溯法#include #include #include typedef struct goods double *value; /價(jià)值 double *weight; /重量 char *select; /是否選中到方案 int num;/物品數(shù)量 double limitw; /限制重量GOODS;double maxvalue,totalvalue; char *select1; void backpack(GOODS *g, int i, double tw, double tv) int k; if (tw + g-we

14、ighti limitw) select1i = 1; if (i num - 1) backpack(g, i + 1, tw + g-weighti, tv); else for (k = 0; k num; +k) g-selectk = select1k;maxvalue = tv; select1i = 0; if (tv - g-valuei maxvalue) if (i num - 1) backpack(g, i + 1, tw, tv - g-valuei); else for (k = 0; k num; +k) g-selectk = select1k;maxvalue

15、 = tv - g-valuei; int main() double sumweight; GOODS g; int i; printf(背包最大重量:); scanf(%lf,&g.limitw); printf(可選物品數(shù)量:); scanf(%d,&g.num); if(!(g.value = (double *)malloc(sizeof(double)*g.num) printf(內(nèi)存分配失敗n); exit(0); if(!(g.weight = (double *)malloc(sizeof(double)*g.num) printf(內(nèi)存分配失敗n); exit(0); if

16、(!(g.select = (char *)malloc(sizeof(char)*g.num) printf(內(nèi)存分配失敗n); exit(0); if(!(select1 = (char *)malloc(sizeof(char)*g.num) printf(內(nèi)存分配失敗n); exit(0); totalvalue=0; for (i = 0; i g.num; i+) printf(輸入第%d號(hào)物品的重量和價(jià)值:,i + 1); scanf(%lf%lf,&g.weighti,&g.valuei); totalvalue+=g.valuei; printf(n背包最大能裝的重量為:%.

17、2fnn,g.limitw); for (i = 0; i g.num; i+) printf(第%d號(hào)物品重:%.2f,價(jià)值:%.2fn, i + 1, g.weighti, g.valuei); for (i = 0; i g.num; i+) select1i=0; maxvalue=0; backpack(&g,0,0.0,totalvalue); sumweight=0; printf(n可將以下物品裝入背包,使背包裝的物品價(jià)值最大:n); for (i = 0; i g.num; +i) if (g.selecti) printf(第%d號(hào)物品,重量:%.2f,價(jià)值:%.2fn,

18、i + 1, g.weighti, g.valuei); sumweight+=g.weighti; printf(n總重量為: %.2f,總價(jià)值為:%.2fn, sumweight, maxvalue ); return 0;四、算法分析（與改進(jìn)）（1）算法實(shí)現(xiàn)的復(fù)雜度在問題規(guī)模很大時(shí)可以接受嗎？答：不可以接受。因?yàn)樵撍惴ㄊ侵笖?shù)級(jí)別的時(shí)間復(fù)雜度為(*2)nOn，當(dāng)n較大時(shí)，也能在一定時(shí)間內(nèi)無(wú)法得出結(jié)果?？臻g復(fù)雜度為()On，還可以接受。但是綜合上面分析，時(shí)間復(fù)雜度成為極大地瓶頸。所以規(guī)模很大時(shí)不可以接受。 （2）所選用的數(shù)據(jù)結(jié)構(gòu)合適嗎？答：合適，只用到一維數(shù)組。使用的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，易理解。能夠?qū)?shù)組中的每個(gè)元素隨機(jī)訪問。（3）該算法都存在哪幾類可能出現(xiàn)的情況，你的測(cè)試完全覆蓋了你所想到的這些 情況嗎，測(cè)試結(jié)果如何？答：測(cè)試全面。輸入規(guī)模為0時(shí)，程序自動(dòng)結(jié)束。輸入總重量小于背包容量時(shí)，結(jié)果為所有物品的價(jià)值總和。輸入的總重量大于背包容量時(shí)，結(jié)果為能