問(wèn)題
二維費(fèi)用的背包問(wèn)題是指：對(duì)于每件物品，具有兩種不同的費(fèi)用溜哮；選擇這件物品必須同時(shí)付出這兩種代價(jià)滔金；對(duì)于每種代價(jià)都有一個(gè)可付出的最大值（背包容量）。問(wèn)怎樣選擇物品可以得到最大的價(jià)值茂嗓。設(shè)這兩種代價(jià)分別為代價(jià)1和代價(jià)2餐茵，第i件物品所需的兩種代價(jià)分別為a[i]和b[i]。兩種代價(jià)可付出的最大值（兩種背包容量）分別為V和U述吸。物品的價(jià)值為w[i]忿族。
算法
費(fèi)用加了一維，只需狀態(tài)也加一維即可蝌矛。設(shè)f[i][v][u]表示前i件物品付出兩種代價(jià)分別為v和u時(shí)可獲得的最大價(jià)值道批。狀態(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)每件物品只可以取一次時(shí)變量```v```和```u```采用逆序的循環(huán)入撒，當(dāng)物品有如完全背包問(wèn)題時(shí)采用順序的循環(huán)隆豹。當(dāng)物品有如多重背包問(wèn)題時(shí)拆分物品。這里就不再給出偽代碼了茅逮，相信有了前面的基礎(chǔ)璃赡，你能夠自己實(shí)現(xiàn)出這個(gè)問(wèn)題的程序判哥。
#####物品總個(gè)數(shù)的限制
有時(shí)，“二維費(fèi)用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品碉考。這事實(shí)上相當(dāng)于每件物品多了一種“件數(shù)”的費(fèi)用塌计，每個(gè)物品的件數(shù)費(fèi)用均為1，可以付出的最大件數(shù)費(fèi)用為M豆励。換句話說(shuō)夺荒，設(shè)f[v][m]表示付出費(fèi)用v瞒渠、最多選m件時(shí)可得到的最大價(jià)值良蒸，則根據(jù)物品的類型（01、完全伍玖、多重）用不同的方法循環(huán)更新嫩痰，最后在f[0..V][0..M]范圍內(nèi)尋找答案。
####小結(jié)
是不是可以用來(lái)解決多重背包的問(wèn)題窍箍？串纺？？只不過(guò)比多重背包復(fù)雜度高
當(dāng)發(fā)現(xiàn)由熟悉的動(dòng)態(tài)規(guī)劃題目變形得來(lái)的題目時(shí)椰棘，在原來(lái)的狀態(tài)中加一維以滿足新的限制是一種比較通用的方法纺棺。希望你能從本講中初步體會(huì)到這種方法。
####轉(zhuǎn)載：dd_engi 的背包九講