【問題】

對于每件物品，具有兩種不同的體積，選擇這件物品必須同時付出這兩種代價，對于每種代價都有一個可付出的最大值（背包容量）。

問：怎樣選擇物品可以得到最大的價值？

設：這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為a[i]和b[i]。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為c[i]。

【算法】

費用加了一維，只需狀態也加一維即可。

設f[i][v][u]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。

狀態轉移方程就是：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+c[i]}

如前述方法，可以只使用二維的數組：當每件物品只可以取一次時變量v和u采用逆序的循環，當物品有如完全背包問題時采用順序的循環。當物品有如多重背包問題時拆分物品。

【物品總個數的限制】

有時，“二維費用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實上相當于每件物品多了一種“件數”的費用，每個物品的件數費用均為1，可以付出的最大件數費用為M。換句話說，設f[v][m]表示付出費用v、最多選m件時可得到的最大價值，則根據物品的類型（01、完全、多重）用不同的方法循環更新，最后在f[0..V][0..M]范圍內尋找答案。

【實現】

設s[i][j][k]表示將前i件物品放入兩種容量分別為j和k的背包時所能獲得的最大價值，則狀態轉移方程為f[i][j][k]=max{f[i-1][j][k], f[i-1][j-v[i]][k-u[i]]+c[i]}，遞推邊界為當i=0時f[i][j][k]=0。和01背包類似，狀態的維數可以輕易的從三維降低到二維，具體實現見下。

for (int i=0; i<=V; i++) // 邊界for (int j=0; j<=U; j++)s[i][j]=0; for (int i=1; i<=N; i++)for (int j=V; j>=v[i]; j--)for (int k=U; k>=u[i]; k--) s[j][k]=max(s[j][k], s[j-v[i]][k-u[i]]+c[i]);

?

總結

以上是生活随笔為你收集整理的动态规划 —— 背包问题 P05 —— 二维背包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。