混合背包
如果將01背包、完全背包、多重背包三個(gè)背包混合起來(lái)，也就是說(shuō)，有的物品只可以取一次（01背包），有的物品可以取無(wú)限次（完全背包），有的物品可以取的次數(shù)有一個(gè)上限（多重背包），應(yīng)該怎么求解呢？
01背包與完全背包的混合
考慮到在01背包和完全背包中給出的偽代碼只有一處不同，即 j 的循環(huán)順序不一樣，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無(wú)限次，那么只需在對(duì)每個(gè)物品應(yīng)用轉(zhuǎn)移方程時(shí)，根據(jù)物品的類別選用順序或逆序的循環(huán)即可，復(fù)雜度是O(VN)。再加上多重背包
如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN)的解法：遇到多重背包類型的物品用單調(diào)隊(duì)列解即可。但如果不考慮超過(guò)NOIPNOIPNOIP范圍的算法的話，用多重背包中將每個(gè)這類物品分成 O(log(p[i])) 個(gè)01背包的物品的方法也已經(jīng)很優(yōu)了。當(dāng)然，更清晰的寫(xiě)法是調(diào)用我們前面給出的三個(gè)相關(guān)過(guò)程。代碼：
m[i]:每個(gè)物品的件數(shù)，0代表無(wú)窮個(gè)
for (int i = 1; i <= n; i++)
if (m[i] == 0)
for (int j = v[i]; j <= V; j++)
f[j] = max(f[j], f[j - v[i]] + p[i]);
else
for (int k = 1; k <= m[i]; k++)
for (int j = V; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + p[i]);
二維費(fèi)用背包
二維費(fèi)用的背包問(wèn)題是指：對(duì)于每件物品，具有兩種不同的費(fèi)用；選擇這件物品必須同時(shí)付出這兩種代價(jià)；對(duì)于每種代價(jià)都有一個(gè)可付出的最大值（背包容量）。問(wèn)怎樣選擇物品可以得到最大的價(jià)值。設(shè)這兩種代價(jià)分別為代價(jià)1和代價(jià)2，第 i 件物品所需的兩種代價(jià)分別為 w[i] 和 g[i]。兩種代價(jià)可付出的最大值（兩種背包容量）分別為 V 和 T。物品的價(jià)值為 v[i]。
算法思路
費(fèi)用加了一維，只需狀態(tài)也加一維即可。
設(shè) [i][j][k] 表示前 i 件物品付出兩種代價(jià)分別為 j 和 k 時(shí)可獲得的最大價(jià)值。
狀態(tài)轉(zhuǎn)移方程就是：
f[i][j][k] = max{ f[i?1][j][k],f[i?1][j?w[i]][k?g[i]]+v[i] }
如前述方法，可以只使用二維的數(shù)組：當(dāng)每件物品只可以取一次時(shí)變量 j 和 k 采用逆序的循環(huán)，當(dāng)物品有如完全背包問(wèn)題時(shí)采用順序的循環(huán)。當(dāng)物品有如多重背包問(wèn)題時(shí)拆分物品。代碼：
算法優(yōu)化
二維費(fèi)用背包也可以進(jìn)行空間復(fù)雜度的優(yōu)化，即使用二維數(shù)組替代三維數(shù)組：
- 當(dāng)每件物品只可以取一次時(shí)變量 j 和 k 采用
逆序循環(huán)
for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
for (int k = T; k >= g[i]; k--)
f[j][k] = max(f[j][k], f[j - v[i]][k - g[i]] + p[i]);
- 物品有如完全背包問(wèn)題時(shí)采用
順序循環(huán) - 當(dāng)物品有如多重背包問(wèn)題時(shí)
拆分物品
分組背包
問(wèn)題描述
有n件物品和一個(gè)容量為V的背包。第i件物品的體積是v[i]，價(jià)值是pv[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
算法思路
這個(gè)問(wèn)題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。
設(shè)f[k][j]表示前 k 組物品放入一個(gè)容量為 j 的背包能獲得的最大價(jià)值，則有：
f[k][j]=max(f[k?1][j],f[k?1][j?v[i]]+p[i]∣物品i屬于組k)
偽代碼如下：
for (所有的組k)
for (int j = V; j >= 0; j--)
for (所有屬于組k的i)
f[j] = max{f[j], f[j - v[i]] + p[i]}
注意for(j...0)這一層循環(huán)必須在for(所有的 i 屬于組k)之外。這樣才能保證每一組內(nèi)的物品最多只有一個(gè)會(huì)被添加到背包中。
嘗試一下例題：
class Solution {
let K:[[Int]] = [[10,10],[50]]
// 價(jià)值
let p:[Int] = [10,5,400]
func findMaxPrice(capital V: Int) -> Int {
var dp = Array(repeating: 0, count: V + 1)
for k in 0..<K.count {
for j in (0...V).reversed() {
let m = K[k]
for i in 0..<m.count {
if j >= m[i] {
dp[j] = max(dp[j], dp[j - m[i]] + p[i])
}
}
}
}
return dp[V]
}
}
輸出10
