問題

二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設(shè)這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為a[i]和b[i]。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為w[i]。

算法

費用加了一維，只需狀態(tài)也加一維即可。設(shè)f[i][v][u]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。狀態(tài)轉(zhuǎn)移方程就是：

f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}```
如前述方法，可以只使用二維的數(shù)組：當(dāng)每件物品只可以取一次時變量```v```和```u```采用逆序的循環(huán)，當(dāng)物品有如完全背包問題時采用順序的循環(huán)。當(dāng)物品有如多重背包問題時拆分物品。這里就不再給出偽代碼了，相信有了前面的基礎(chǔ)，你能夠自己實現(xiàn)出這個問題的程序。
#####物品總個數(shù)的限制
有時，“二維費用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實上相當(dāng)于每件物品多了一種“件數(shù)”的費用，每個物品的件數(shù)費用均為1，可以付出的最大件數(shù)費用為M。換句話說，設(shè)f[v][m]表示付出費用v、最多選m件時可得到的最大價值，則根據(jù)物品的類型（01、完全、多重）用不同的方法循環(huán)更新，最后在f[0..V][0..M]范圍內(nèi)尋找答案。
####小結(jié)
是不是可以用來解決多重背包的問題？？？只不過比多重背包復(fù)雜度高
當(dāng)發(fā)現(xiàn)由熟悉的動態(tài)規(guī)劃題目變形得來的題目時，在原來的狀態(tài)中加一維以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。
####轉(zhuǎn)載：dd_engi 的背包九講