编辑“︁多重背包问题”︁

{{Note|本文是[[数据结构与算法学习路径结构]]中[[动态规划]]章节的一部分，主要介绍多重背包问题的定义、解法及优化方法。}}

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

== 问题定义 ==
给定：
* 背包容量 <math>W</math>
* <math>n</math> 种物品，每种物品有三个属性：
  * 重量 <math>w_i</math>
  * 价值 <math>v_i</math>
  * 最大可用数量 <math>s_i</math>

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

=== 数学表达 ===
<math>
\begin{cases}
\text{最大化} & \sum_{i=1}^{n} v_i x_i \\
\text{约束条件} & \sum_{i=1}^{n} w_i x_i \leq W \\
               & 0 \leq x_i \leq s_i \quad (x_i \in \mathbb{Z})
\end{cases}
</math>

== 基本解法 ==
=== 动态规划思路 ===
使用二维状态数组 <math>dp[i][j]</math> 表示前 <math>i</math> 种物品在背包容量为 <math>j</math> 时的最大价值。

状态转移方程：
<math>
dp[i][j] = \max \begin{cases}
dp[i-1][j], \\
dp[i-1][j - k \cdot w_i] + k \cdot v_i \quad (1 \leq k \leq \min(s_i, \lfloor j/w_i \rfloor))
\end{cases}
</math>

=== 代码实现 ===
<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 优化方法 ==
=== 二进制拆分优化 ===
将每种物品的数量 <math>s_i</math> 拆分为 <math>1, 2, 4, ..., 2^{k-1}, s_i - 2^k + 1</math> 的组合，转化为01背包问题。

示例：
* 某物品有13件 → 拆分为1, 2, 4, 6四个"新物品"
* 时间复杂度从 <math>O(n \cdot W \cdot S)</math> 降为 <math>O(n \cdot W \cdot \log S)</math>

=== 空间优化 ===
使用滚动数组将空间复杂度从 <math>O(nW)</math> 降为 <math>O(W)</math>：
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

== 实际应用案例 ==
'''物流装箱问题'''：
* 有若干种货物（每种有固定数量）
* 卡车有最大载重限制
* 需要选择货物组合使运输价值最大化

<mermaid>
graph TD
    A[货物A: 重量2,价值3,数量3] -->|选择2件| B(总重量4,价值6)
    C[货物B: 重量3,价值4,数量2] -->|选择1件| D(总重量7,价值10)
    E[货物C: 重量4,价值5,数量1] -->|选择0件| F(最终组合)
</mermaid>

== 复杂度分析 ==
{| class="wikitable"
|-
! 方法 !! 时间复杂度 !! 空间复杂度
|-
| 基本动态规划 || <math>O(n \cdot W \cdot S)</math> || <math>O(nW)</math>
|-
| 二进制优化 || <math>O(n \cdot W \cdot \log S)</math> || <math>O(W)</math>
|}

== 常见问题 ==
{{Q&A
|问题1 = 多重背包与完全背包的区别是什么？
|答案1 = 多重背包中每种物品有数量限制<math>s_i</math>，而完全背包每种物品可以无限取用。
|问题2 = 为什么二进制拆分能保证正确性？
|答案2 = 任何正整数都可以表示为2的幂次和，拆分后能组合出所有可能的选取数量。
}}

== 扩展练习 ==
1. 修改代码处理重量为小数的情况<br>
2. 实现输出具体选取方案的功能<br>
3. 研究存在「物品依赖性」时的变种问题

{{Algorithm-stub}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]