在這個專題，我為大家?guī)砹艘粋€動態(tài)規(guī)劃中的經(jīng)典得不能再經(jīng)典的問題——背包問題，在這個專題我打算講三類背包問題：01背包、完全背包、多重背包。廢話不多說，那我就開始講解吧O(∩_∩)O~！

01背包問題：

有n個物品，每個物品的重量為weight[i]，每個物品的價值為value[i]。現(xiàn)在有一個背包，它所能容納的重量為total，問：當(dāng)你面對這么多有價值的物品時，你的背包所能帶走的最大價值是多少？

思路：每個物品無非是裝入背包或者不裝入背包，那么就一個一個物品陸續(xù)放入背包中，可以有：狀態(tài)轉(zhuǎn)移方程：

tab[i][j] = max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j]) ({i,j|0<i<=n,0<=j<=total})

其中i表示放第i個物品，j表示背包所容納的重量，那么tab[i-1][j-weight[i]]+value[i]表示放入第i物品，剛開始接觸會有疑問，tab[i-1][j-weight[i]]這個值，可以這樣理解：tab[i-1][j]為裝到上一個物品在背包j容量時的最佳值，那么如果我要求在j容量的時候放入現(xiàn)在的i物品的價值，那么是不是要先得到容量為(j-weight[i])時候的價值，即先得到tab[i-1][j-weight[i]]，所以 tab[i-1][j-weight[i]]+value[i] 為放入第i物品的價值； tab[i-1][j] 就是不放入第i個物品

動態(tài)規(guī)劃的思維就在這里體現(xiàn)了，即tab[i-1][j]是tab[i][j]的最優(yōu)解(我覺得上面的思路講解較容易理解)。

例子：5個物品，(重量，價值)分別為：(5，12)，(4，3)，(7，10)，(2，3)，(6，6)。

故有：

1 for i=[weight[0],total] 2 tab[n-1][i]=weight[0]; //n為物品數(shù)量 3 for i=[1,n) 4 for j=[weight[i],total] 5 tab[n-i-1][j]= max(tab[n-i][j-weight[i]]+value[i],tab[n-i][j]) 6 /* print tab[0][total] */

完全背包問題：

有n種物品，每種物品有無限個，每個物品的重量為weight[i]，每個物品的價值為value[i]。現(xiàn)在有一個背包，它所能容納的重量為total，問：當(dāng)你面對這么多有價值的物品時，你的背包所能帶走的最大價值是多少？

有了上面01背包的式子，這題會變的容易理解很多，只是這個式子要有小小的改動。01背包在二維數(shù)組上操作，就是為了防止一個物品被放入多次的情況。因此一維數(shù)組可以滿足完全背包的問題。如下：

tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);({i,j|0<i<=n,0<=j<=total})

根本就是一樣的，只不過物品可以被放多次。

故有：

1 for i=[0,n) 2 for(j=weight[i];j<=total;j++) 3 tab[j]=max(tab[j-weight[i]]+value[i],tab[j]) 4 /* print tab[0][total] */

多重背包問題：

有n種物品，每種物品有amount[i]個，每個物品的重量為weight[i]，每個物品的價值為value[i]。現(xiàn)在有一個背包，它所能容納的重量為total，問：當(dāng)你面對這么多有價值的物品時，你的背包所能帶走的最大價值是多少？

多重和完全更接近，多了數(shù)量的限制，用一個count[n]計(jì)數(shù)數(shù)組來限制物品i的數(shù)量。當(dāng)放入第i個物品是較優(yōu)值的時候，count[i]=count[j-weight[i]]+1)j 的含義請查看代碼);這樣做是因?yàn)?#xff0c;放入第i個物品的操作是基于count[j-weight[i]]放入的，所以當(dāng)count[i-weight[i]]>=amount[i]時，就要阻止放入即便放入第i個物品是較優(yōu)值。

故有：

1 for i=[0,n) /*將count數(shù)組清零*/ 2 for(j=weight[i];j<=total;j++) 3 if(count[j-weight[i]]<amout[i]) 4 tab[j]=max(tab[j-weight[i]]+value[i],tab[j]); 5 if(tab[j]=tab[j-weight[i]]+value[i]) 6 //決定放入i是較優(yōu)解 7 count[i]=count[j-weight[i]]+1 8 else if(tab[j]=0) //防止裝第1個物品和裝其他物品的情況 9 tab[j]=tab[j-1],count[j]=count[j-1] 10 else count[j]=count[j-1] 11 /* print tab[0][total] */

?

轉(zhuǎn)載于:https://www.cnblogs.com/geek-007/p/6749688.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的专题——背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。