多重背包问题是完全背包问题的进阶问题，现实中更多见，也值得深入研究。
有 n 种物品和一个容量为 V 的背包。第 i 种物品最多有 Mi 件可用，每件耗费的空间是 Ci ，价值是 Wi。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
这题目和完全背包问题很类似。基本的状态转移方程只需将完全背包问题的方程略微一改
即可：
1
| dp[i][j] = max{dp[i − 1][j − k * Ci] + k * Wi (0 ≤ k ≤ Mi) }
|
基本的解题方法就是采用完全背包中的“二进制分解法”，将 Mi 进行二进制分解，转化为 01 背包问题。另外，还要注意就是当 Ci * Mi ≥ V 时，编号为 i 的物品放入的情况实际和完全背包相同，无需进行转换。
最后，得到伪代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void multiplePack(cost, weight, max)
if cost * max >= V
completePack(cost, weight)
return
int k = 1
while max > k
zeroOnePack(k * cost, k * weight)
max -= k
k *= 2
zeroOnePack(max * cost, max * weight)
int calculate(n, V)
for i = 1 .. n
multiplePack(Ci, Wi, Mi)
return dp[V]
|
如果题目要求必须是恰好装满背包，而且只问是否有可行的装满方案时，多重背包问题可以有时间复杂度为 O(V * n) 的解法。
这个解法的状态缓存数组不同于基本的多重背包问题的构造方法，要使用 dp[i][j] 来表示使用编号 1 到 i 的物品恰好填满容积为 j 的背包后，还剩余多少个编号为 i 的物品。
这样可以知道初始状态 dp[0][0] 为 0，而 dp[0][1 .. V] 都为 -∞。
而且，不难推断：当前 i - 1 个物品可以恰好填满容积为 j 的背包时，会剩余 Mi 个编号为 i 的物品；当前 i 个物品恰好填满容积为 j - Ci 的背包时，剩余的编号 i 的物品的个数再减去 1，就是恰好填满容积为 j 的背包时，剩余的编号为 i 的物品的个数。
最后，可以得到状态转移方程：
1
2
3
4
5
| dp[0][0] = 0
dp[0][1 .. V] = -∞
dp[i][j] = Mi (dp[i - 1][j] ≥ 0)
-∞ (j < Ci 或 dp[i - 1][j - Ci] ≤ 0)
dp[i - 1][j - Ci] - 1 (其他情况)
|
这样，可以得到伪代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int[][] dp = new int[n + 1][V + 1]
dp[0][0] = 0
for i = 1 .. V
dp[0][i] = -1
for i = 1 .. n
for j = 0 .. V
if dp[i - 1][j] >= 0
dp[i][j] = Mi
else
dp[i][j] = -1
for j = 0 .. V - Ci
if dp[i][j] > 0
dp[i][j + Ci] = max(dp[i][j + Ci], dp[i][j] - 1)
|
最后，如果 dp[n][V] 不小于 0 则说明可以恰好填满容量为 V 的背包。
进行空间优化则可以得到伪代码：
1
2
3
4
5
6
7
8
9
10
11
12
| int[] dp = new int[V + 1]
dp[0] = 0
dp[1 .. V] = -1
for i = 1 .. n
for j = 0 .. V
if dp[j] >= 0
dp[j] = Mi
else if j < Ci || dp[j - Ci] <= 0
dp[j] = -1
else
dp[j] = dp[j - Ci] - 1
|
背包问题九讲