【概述】

完全背包問題也是一個(gè)相當(dāng)基礎(chǔ)的背包問題，它有兩個(gè)狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。

【題目】

有N種物品和一個(gè)容量為V的背包，每種物品都有無限件可用。第i種物品的體積是w[i]，價(jià)值是c[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。

【基本思路】

這個(gè)問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。

如果仍然按照解01背包時(shí)的思路，令f[i][v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：f[i][v]=max{ f[i-1][v-k*w[i]] + k*c[i] } (0<=k*w[i]<=v)

這跟01背包問題一樣有O(N*V)個(gè)狀態(tài)需要求解，但求解每個(gè)狀態(tài)的時(shí)間已經(jīng)不是常數(shù)了，求解狀態(tài)f[i][v]的時(shí)間是O(v/w[i])，總的復(fù)雜度是超過O(VN)的。

將01背包問題的基本思路加以改進(jìn)，得到了這樣一個(gè)清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進(jìn)這個(gè)復(fù)雜度。

【簡(jiǎn)單有效的優(yōu)化】

若兩件物品i、j滿足w[i]<=w[j]且c[i]>=c[j]，則將物品j去掉，不用考慮。

原因：任何情況下都可將價(jià)值小費(fèi)用高得j換成物美價(jià)廉的i，得到至少不會(huì)更差的方案。對(duì)于隨機(jī)生成的數(shù)據(jù)，這個(gè)方法往往會(huì)大大減少物品的件數(shù)，從而加快速度。然而這個(gè)并不能改善最壞情況的復(fù)雜度，因?yàn)橛锌赡芴貏e設(shè)計(jì)的數(shù)據(jù)可以一件物品也去不掉。

這個(gè)優(yōu)化可以簡(jiǎn)單的O(N^2)地實(shí)現(xiàn)，一般都可以承受。

另外，針對(duì)背包問題而言，比較不錯(cuò)的一種方法是：首先將費(fèi)用大于V的物品去掉，然后使用類似計(jì)數(shù)排序的做法，計(jì)算出費(fèi)用相同的物品中價(jià)值最高的是哪個(gè)，可以O(shè)(V+N)地完成這個(gè)優(yōu)化。

【轉(zhuǎn)化為01背包問題求解】

既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。

最簡(jiǎn)單的想法是，考慮到第i種物品最多選V/w[i]件，于是可以把第i種物品轉(zhuǎn)化為V/w[i]件費(fèi)用及價(jià)值均不變的物品，然后求解這個(gè)01背包問題。

雖然這樣沒有改進(jìn)基本思路的時(shí)間復(fù)雜度，但這給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。

更高效的轉(zhuǎn)化方法是：將第i種物品拆成費(fèi)用為w[i]*2^k、價(jià)值為c[i]*2^k的若干件物品，其中k滿足w[i]*2^k<=V

原因：這是二進(jìn)制的思想，不管最優(yōu)策略選幾件第i種物品，總可以表示成若干個(gè)2^k件物品的和。這樣把每種物品拆成O(log(V/w[i]))件物品，是一個(gè)很大的改進(jìn)。

【O(VN)的算法】

這個(gè)算法使用一維數(shù)組

偽代碼

for i=1..Nfor v=0..Vf[v]=max{f[v],f[v-weight]+cost}

你會(huì)發(fā)現(xiàn)，這個(gè)偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？

首先想想為什么P01中要按照v=V..0的逆序來循環(huán)。這是因?yàn)橐ＷC第i次循環(huán)中的狀態(tài)f[i][v]是由狀態(tài)f[i-1][v-w[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時(shí)，依據(jù)的是一個(gè)絕無已經(jīng)選入第i件物品的子結(jié)果f[i-1][v-w[i]]。而現(xiàn)在完全背包的特點(diǎn)恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時(shí)，卻正需要一個(gè)可能已選入第i種物品的子結(jié)果f[i][v-w[i]]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個(gè)簡(jiǎn)單的程序?yàn)楹纬闪⒌牡览怼?/p>

這個(gè)算法也可以以另外的思路得出。

例如，基本思路中的狀態(tài)轉(zhuǎn)移方程可以等價(jià)地變形成這種形式：f[i][v]=max{ f[i-1][v] , f[i][v-w[i]]+c[i] }

將這個(gè)方程用一維數(shù)組實(shí)現(xiàn)，便得到了上面的偽代碼。

最后抽象出處理一件完全背包類物品的過程偽代碼

procedure CompletePack(cost,weight)for v=weight..Vf[v]=max{f[v],f[v-weight]+cost

?

總結(jié)

以上是生活随笔為你收集整理的动态规划 —— 背包问题 P02 —— 完全背包的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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