多重背包问题[编辑 | 编辑源代码]

多重背包问题（Multiple Knapsack Problem）是背包问题的扩展形式之一，其特点是每种物品有固定的数量限制（既不是无限取用的完全背包，也不是只能取0或1次的01背包）。该问题在资源分配、生产调度等领域有广泛应用。

问题定义[编辑 | 编辑源代码]

给定：

背包容量 $W$
$n$ 种物品，每种物品有三个属性：

 * 重量  $w_{i}$ 
 * 价值  $v_{i}$ 
 * 最大可用数量  $s_{i}$

目标：选择物品装入背包，使得总重量不超过 $W$ 且总价值最大。

数学表达[编辑 | 编辑源代码]

${\begin{cases} 最大化 & \sum_{i = 1}^{n} v_{i} x_{i} \\ 约束条件 & \sum_{i = 1}^{n} w_{i} x_{i} \leq W \\ 0 \leq x_{i} \leq s_{i} (x_{i} \in ℤ) \end{cases}$

基本解法[编辑 | 编辑源代码]

动态规划思路[编辑 | 编辑源代码]

使用二维状态数组 $d p [i] [j]$ 表示前 $i$ 种物品在背包容量为 $j$ 时的最大价值。

状态转移方程： $d p [i] [j] = \max {\begin{cases} d p [i - 1] [j], \\ d p [i - 1] [j - k \cdot w_{i}] + k \cdot v_{i} (1 \leq k \leq \min (s_{i}, ⌊ j / w_{i} ⌋)) \end{cases}$

代码实现[编辑 | 编辑源代码]

def multiple_knapsack(W, weights, values, counts):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(W + 1):
            max_k = min(counts[i-1], j // weights[i-1])
            dp[i][j] = max(
                dp[i-1][j - k * weights[i-1]] + k * values[i-1]
                for k in range(0, max_k + 1)
            )
    
    return dp[n][W]

# 示例
W = 10
weights = [2, 3, 4]
values = [3, 4, 5]
counts = [3, 2, 1]
print(multiple_knapsack(W, weights, values, counts))  # 输出：13

优化方法[编辑 | 编辑源代码]

二进制拆分优化[编辑 | 编辑源代码]

将每种物品的数量 $s_{i}$ 拆分为 $1, 2, 4, . . ., 2^{k - 1}, s_{i} - 2^{k} + 1$ 的组合，转化为01背包问题。

示例：

某物品有13件 → 拆分为1, 2, 4, 6四个"新物品"
时间复杂度从 $O (n \cdot W \cdot S)$ 降为 $O (n \cdot W \cdot \log S)$

空间优化[编辑 | 编辑源代码]

使用滚动数组将空间复杂度从 $O (n W)$ 降为 $O (W)$ ：

def optimized_multiple_knapsack(W, weights, values, counts):
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        # 二进制拆分
        k = 1
        remaining = counts[i]
        while k <= remaining:
            w = k * weights[i]
            v = k * values[i]
            for j in range(W, w - 1, -1):
                dp[j] = max(dp[j], dp[j - w] + v)
            remaining -= k
            k *= 2
        if remaining > 0:
            w = remaining * weights[i]
            v = remaining * values[i]
            for j in range(W, w - 1, -1):
                dp[j] = max(dp[j], dp[j - w] + v)
    
    return dp[W]