資源描述：
《本周算法：背包問題-Java開發(fā)Java經(jīng)驗(yàn)技巧》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、木周算法：背包問題-編程開發(fā)技術(shù)本周算法：背包問題木文由ImportNew?hejiani翻譯自javacodegeeks<>歡迎加入翻譯小組。轉(zhuǎn)載請(qǐng)見文末要求。背包問題很冇意思，同時(shí)也富冇挑戰(zhàn)性。首先看一下這個(gè)問題的完整描述：?jiǎn)栴}假定背包的最大容量為w,N件物品，毎件物品都有自己的價(jià)值和重量，將物品放入背包屮使得背包內(nèi)物品的總價(jià)值最大。背包問題wiki可以想彖這樣一個(gè)場(chǎng)景一一小偷在屋子里偷東西，他帶著一只背包。屋子里物品數(shù)量有限——每件物詁都具有一定的重量和價(jià)值——珠寶重量輕但價(jià)值高，桌子重但價(jià)值低。最重要的是小偷背包容
2、量有限。很明顯，他不能把桌子分成兩份或者帶走珠寶的3/4o對(duì)于一件物甜他只能選擇帶走或者不帶走。示例:KnapsackMaxweightTotalitemsValuesofitemsW二10(units)N=4v[]={10,40,30,50}從示例數(shù)據(jù)大致估算一下，最大重量為10時(shí)苗包能容納的物品最大價(jià)值為50+40=90,重量為7。解決方法：最佳的解決方法是使用動(dòng)態(tài)規(guī)劃一一先得到該問題的局部解然后擴(kuò)展到全局問題解。構(gòu)建物品X在不同重量時(shí)的價(jià)值數(shù)組V（Value數(shù)組）:V[N][W]二4rows*10columns該矩陣
3、中的每個(gè)值的求解都代表一個(gè)更小的背包問題。初始情況一：對(duì)于第0列，它的含義是背包的容量為0。此時(shí)物品的價(jià)值呢？沒有。因此，第一列都填入0。初始情況二：對(duì)于第0行，它的含義是屋內(nèi)沒有物站。那么沒有任何物品的背包里的價(jià)值多少呢？還是沒有！所有都是0。步驟：1、現(xiàn)在，開始填入數(shù)組每一行的值。第1行第1列代表什么含義呢？對(duì)于第一個(gè)物品，可以把重量為1的該物品放入背包嗎？不行。第一個(gè)物品的重量是5。因此，填入0。實(shí)際上直到第5列（重量5）之前都應(yīng)該填入0。2、對(duì)于第1行的第5列（重量5），意味著將物品1放入背包。填入10（注意,這是
4、Value數(shù)組）：3、繼續(xù)，對(duì)于第6列，我們可以再放入重量為1（重量值-物品的重量）的物品嗎。我們現(xiàn)在只考慮物品k由于我們加入物品1Z后就不能再加入額外的重量,可以很直觀地看到其余的列都應(yīng)該還是相同的值。4、接著，冇意思的事情就要出現(xiàn)了。在第3行第4列，此時(shí)重量為4。需要作以下判斷：1.可以放入物品2嗎——可以。物品2的重量為402.不加入物品2的話當(dāng)前已有物品的重量的Value值是否更人——杏看相同重雖時(shí)的詢-?行的值。不是。詢一行的值為0,重量4時(shí)不能放入物品1。3.在這個(gè)重量時(shí)可以放入兩件物品使得價(jià)值最大嗎？——不能
5、。此時(shí)重量減去物品2的重最后為0o為什么是前一行?簡(jiǎn)單來說，重量為4的前一行的值木身就是個(gè)更小的背包問題解，它的含義是到該重量時(shí)背包內(nèi)物品的最大價(jià)值（通過遍歷物品得到）。舉個(gè)例子：1.當(dāng)前物品價(jià)值=402.當(dāng)前物品重量二41.剩余重量=4-4二02.查看上而的行（物品1或者其余行的值）。剩余容量為0時(shí)，可以再容納物品1嗎?對(duì)于該給定的重量值上面的行還有任何值嗎？計(jì)算過程如下：1）計(jì)算不放入該物品時(shí)該重量的最大價(jià)值:previousrow,sameweight二0=>V[item~l][weight]2）計(jì)算當(dāng)前物品的價(jià)值+
6、可以容納的剩余重量的價(jià)值Valueofcurrentitem+valueinpreviousrowwithweight4（totalweightunti1now（4）-weightofthecurrentitem（4））=>val[item-1]+V[item-1][weight-wt[item-1]]找到二者之中的最大值40（0和40）o3）下一次最重要的位置為第2行第9列。意味著此時(shí)重量為9,放入兩件物品。根據(jù)示例數(shù)據(jù)現(xiàn)在可以放入兩件物品。我們作了以下判斷：1.Thevalueofthecurrentitem=402.
7、Theweightofthecurrentitem二43.Theweightthatisleftover二9-4二54.Checktherowabovc.Atthercmainingweight5,arcweabletoaccommodateItem1.計(jì)算如下：1.不加入該物晶時(shí)該重量的最大價(jià)值：previousrow,sameweight=101.計(jì)算當(dāng)前物品的價(jià)值+可以容納的剩余重量的價(jià)值Valueofcurrentitem(40)+valueinpreviousrowwithweight5(totalweightu
8、ntilnow(9)-weightofthecurrentitem(4))二1010vs50二50o解決了所有的子問題之后，返回V[N][W]的值一一4件物品重量為10時(shí)：復(fù)雜度解法的復(fù)朵度非常直觀。在N次循環(huán)中有W次循環(huán)二〉0(NW)實(shí)現(xiàn)Java代碼實(shí)現(xiàn):classKnapsack{publicsta
