動(dòng)態(tài)規(guī)劃算法-01背包問(wèn)題

動(dòng)態(tài)規(guī)劃法求解。?1背包問(wèn)題一、動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想動(dòng)態(tài)規(guī)劃法是數(shù)學(xué)--“運(yùn)籌學(xué)”中一個(gè)決策分析的實(shí)現(xiàn)，廣泛運(yùn)用在計(jì)算機(jī)算法、企業(yè)決策、市場(chǎng)營(yíng)銷等領(lǐng)域動(dòng)態(tài)規(guī)劃法是將待求解的問(wèn)題分成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)過(guò)分解的子問(wèn)題往往不是獨(dú)立的。若用分治法求解這類問(wèn)題，則相同的子問(wèn)題會(huì)被求解多次，以至于最后解決問(wèn)題需要消耗指數(shù)級(jí)別的時(shí)間。然而，不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。如果能夠保存已經(jīng)解決的子問(wèn)題的答案，在需要時(shí)再找出己經(jīng)求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間的算法。為了達(dá)到這個(gè)目的，可以使用個(gè)表來(lái)記錄已經(jīng)解決子問(wèn)題的答案，不管子問(wèn)題以后是否被用到，只要它計(jì)算過(guò)，就將其結(jié)果填入表中，這就是動(dòng)態(tài)規(guī)劃法的基本思路動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。這類問(wèn)題中，可能會(huì)有許多可行的解，每個(gè)解對(duì)應(yīng)個(gè)值，我們希望找到最大值或者最小值的那個(gè)解，其步驟如下：1、找出最優(yōu)值的性質(zhì)，并分析其結(jié)構(gòu)特征2、遞歸定義最優(yōu)解的值3、自底向上的方式計(jì)算出最優(yōu)值4、根據(jù)計(jì)算最優(yōu)值得到的信息，構(gòu)造一個(gè)最優(yōu)解步驟1—2是基本步驟，在只需求出最優(yōu)值的情況下步驟4可以省略。若需要求子問(wèn)題的最優(yōu)解，則必須執(zhí)行步驟4,此時(shí)在步驟3中計(jì)算最優(yōu)值時(shí)，通常記錄等多的信息，以便在步驟4中根據(jù)所記錄的信息快速構(gòu)造出一個(gè)最優(yōu)解動(dòng)態(tài)規(guī)劃算法是非常有效的算法技術(shù)，那么什么時(shí)候使用它呢？或者說(shuō)其運(yùn)用場(chǎng)景是什么？若求解問(wèn)題具有一下性質(zhì)，可以考慮使用動(dòng)態(tài)規(guī)劃法：1、最優(yōu)子結(jié)構(gòu)：如果一個(gè)問(wèn)題的最優(yōu)解中包含其子問(wèn)題的最優(yōu)解，就是說(shuō)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)。這時(shí)候貪婪算法可能也使用求解此類問(wèn)題2、重疊子問(wèn)題：重疊子問(wèn)題是指用來(lái)求解問(wèn)題的遞歸算法可以反復(fù)的解同樣的問(wèn)題，而不是總在產(chǎn)生新的問(wèn)題，即當(dāng)一個(gè)遞歸算法不斷的調(diào)用同一個(gè)問(wèn)題時(shí)，就說(shuō)該問(wèn)題包含重疊子問(wèn)題，此時(shí)若使用分治法遞歸求解時(shí)，則每次遇到子問(wèn)題都會(huì)視為新問(wèn)題，會(huì)極大降低效率，而動(dòng)態(tài)規(guī)劃法對(duì)每個(gè)子問(wèn)題僅計(jì)算一次，把解保存到在一個(gè)需要時(shí)就可以查看的表中二、動(dòng)態(tài)規(guī)劃法案例：。-1背包問(wèn)題有n個(gè)物品，第i個(gè)物品的價(jià)值為Vi,重量為Wi,其中Vi和Wi均為非負(fù)數(shù)，背包容量為W,W為非負(fù)數(shù)?，F(xiàn)考慮如何選擇裝入背包的物品，使裝入背包的物品總價(jià)值最大。假設(shè)商品有5件，n=5,容量為17,W=17要裝入的物品及其價(jià)值如卜.表所示:物品編號(hào)12345價(jià)值V45101113重量W34789（一）、求解思路1、使用矩陣規(guī)劃出最優(yōu)解把求解過(guò)程看作是一系列的決策過(guò)程，即決定哪些物品應(yīng)該放入背包，哪些物品不放入背包（1）如果一個(gè)問(wèn)題的最優(yōu)解包含了物品n,即Xn=l,那么其余的XI,X2，.…Xn-1一定構(gòu)成子問(wèn)題1,2.......n-1在容量為W-wn時(shí)的最優(yōu)解（2）如果這個(gè)最優(yōu)解不包含物品n,即Xn=O,那么其余X1,X2Xn-1一定構(gòu)成子問(wèn)題1,2n-1在容量為W時(shí)的最優(yōu)解根據(jù)上述分析，設(shè)c[i,w]表示背包容量為w時(shí)i個(gè)物品最優(yōu)解的總價(jià)值，得到公式：0i=0或w=0C[i,w]=-Sc[i-1zw]wi>wmax(c[i-1,w-wi]+vizc[i-1,w]}i>0且wi<=wJ2、根據(jù)物品的件數(shù)i=5、包的容量W=17規(guī)劃“價(jià)值”分布矩陣，如下圖所示:（1）物品價(jià)值重量關(guān)系表物品第1件第2件第3件第4件第5件價(jià)值V45101113重量V34789（2）物品件數(shù)一價(jià)值分布矩陣物品重量01234567891011121314151617池入第1件1000444444444444444放入第2件200045559999999g敬入第3件30004=55510101014：15151519191919被入第4件400045551011111415161&19212121仙入第5件500045551011131415171819212324（-）程序?qū)崿F(xiàn)1、Java語(yǔ)言代碼實(shí)現(xiàn)如下:publicstaticvoidmain(String[]args){int[]goods_weight={3,4,7,8,9};//物品重量int[]goods_value={4,5,10,11,13};//物品價(jià)值intm=17;//背包容量intn=5;//物品個(gè)數(shù)//C[i][j]表示前i個(gè)物品能裝入容量為也的背包中的最大價(jià)值intc[][]=newint[n+1][m+1]；intpath[][]=newint[n+1][m+1]；//初始化第一列和第一行for(inti=0;i<c.length;i++)(c[i][0]=0;}for(inti=0;i<c[0].length;i++){c[0][i]=0;}//通過(guò)公式迭代計(jì)算for(inti=l;i<c.length;i++)(for(intWj=l;Wj<c[0].length;Wj++)(if(goods_weight[i-1]>Wj)c[i][Wj]=c[i-l][Wj];else(if(c[i-1][Wj]<c[i-1][Wj-goods_weight[i-1]]+goods_valuetill)(_-c[i][Wj]=c[i-1][Wj-goods_weight[i-1]]4-goods_value[i-1];path[i][Wj]=1;}else(c[i][Wj]=c[i-l][Wj];}})}for(inti=0;i<c.length;i++)(for(intj=O;j<c[O].length;j++)(System.out.print(c[i][j]+nn);)System.out.printIn();}inti=c.length-1;intj=c[0].length-1;while(i>0&&j>0)(if(path[i][j]==1){System?out?print(”第”+i+”個(gè)物裝入”);j-=goods_weight[i-1];)-i--;})2、C/C++代碼實(shí)現(xiàn)如下：int**demo(intn,intWJnt*WeightsJIoat*Values)(inti,w;〃為二維數(shù)組申請(qǐng)空間int**c=(int**)malloc(sizeof(int*)*(n+l));for(i=0;i<=n;i++)c[i]=(int*)malloc(sizeof(int)*(W+l));〃初始化二維數(shù)組for(w=0;w<=W;w++)c[0][w]=0;for(i=l;i<=n;i++)(c[i][0]=0;for(w=l;w<=W;w++)(〃如果背包剩余重量大于物品重量if(Weights[i-l]<=w){if(Values[i-l]+c[i-l][w-Weights[i-