混合背包
如果将01背包、完全背包、多重背包三个背包混合起来，也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包），应该怎么求解呢？
-
01背包与完全背包的混合
考虑到在01背包和完全背包中给出的伪代码只有一处不同，即 j 的循环顺序不一样，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。 -
再加上多重背包
如果再加上有的物品最多可以取有限次，那么原则上也可以给出O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIPNOIPNOIP范围的算法的话，用多重背包中将每个这类物品分成 O(log(p[i])) 个01背包的物品的方法也已经很优了。当然，更清晰的写法是调用我们前面给出的三个相关过程。代码：
m[i]:每个物品的件数，0代表无穷个
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]);
二维费用背包
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第 i 件物品所需的两种代价分别为 w[i] 和 g[i]。两种代价可付出的最大值（两种背包容量）分别为 V 和 T。物品的价值为 v[i]。
算法思路
费用加了一维，只需状态也加一维即可。
设 [i][j][k] 表示前 i 件物品付出两种代价分别为 j 和 k 时可获得的最大价值。
状态转移方程就是：
f[i][j][k] = max{ f[i−1][j][k],f[i−1][j−w[i]][k−g[i]]+v[i] }
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量 j 和 k 采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。代码：
算法优化
二维费用背包也可以进行空间复杂度的优化，即使用二维数组替代三维数组：
- 当每件物品只可以取一次时变量 j 和 k 采用
逆序循环
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]);
- 物品有如完全背包问题时采用
顺序循环 - 当物品有如多重背包问题时
拆分物品
分组背包
问题描述
有n件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是pv[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法思路
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。
设f[k][j]表示前 k 组物品放入一个容量为 j 的背包能获得的最大价值，则有：
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)这一层循环必须在for(所有的 i 属于组k)之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
尝试一下例题：
class Solution {
let K:[[Int]] = [[10,10],[50]]
// 价值
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
网友评论