多重背包

GGBOND2025/11/11大约 6 分钟

问题描述

给定 N 种物品 和一个容量为 V 的背包。

第 i 种物品：

体积为 vi
价值为 wi
最多可选 si 件

要求选择若干物品装入背包，使得：

物品总体积 ≤ V
总价值最大

输出最大价值。

输入格式


N V
v1 w1 s1
v2 w2 s2
...
vN wN sN

输出格式


一个整数，表示最大总价值

示例输入

示例输出

🧠 思路分析（动态规划五部曲）

① 确定 dp 数组及其含义

状态定义：dp[j] 表示背包容量为 j 时能够获得的最大价值。

使用一维数组优化空间复杂度
j 的取值范围：0 ≤ j ≤ V
最终答案：max(dp[0], dp[1], ..., dp[V])

② 确定状态转移方程

核心思想：对于每种物品，枚举选择的数量（0 到 s_i 件）。

朴素状态转移方程：

dp[j] = max(dp[j], dp[j - k*v_i] + k*w_i)  (0 ≤ k ≤ s_i 且 k*v_i ≤ j)

单调队列优化后的状态转移：

dp[j] = max( dp[k] + (j - k)/v_i * w_i )  (k ≤ j 且 (j - k)/v_i ≤ s_i)

③ 确定初始条件

边界条件：

dp[0] = 0（容量为0时价值为0）
其他位置初始化为0（表示初始状态下最大价值为0）

④ 确定遍历顺序

遍历策略：

外层循环：遍历物品 i = 1 → N
中层循环：按余数分组 mod = 0 → v_i-1
内层循环：在余数组内滑动窗口 j = mod → V（步长 v_i）

关键点：使用单调队列维护窗口内的最优决策。

⑤ 举例推导验证

以示例数据为例：

N=4, V=5
物品1: v=1, w=2, s=3
物品2: v=2, w=4, s=1
物品3: v=3, w=4, s=3
物品4: v=4, w=5, s=2

通过模拟DP过程，最终得到最大价值为10。

💻 Java 实现（单调队列优化）

import java.util.*;

/**
 * 多重背包问题 - 单调队列优化版本
 * 时间复杂度：O(N × V)
 * 空间复杂度：O(V)
 */
public class Main {
    static int N, V;                    // 物品数量N，背包容量V
    static int[] v, w, s;               // 物品的体积、价值、数量限制
    static int[] dp, g;                  // dp数组和临时数组

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入数据
        N = sc.nextInt();
        V = sc.nextInt();

        // 初始化数组（索引从1开始）
        v = new int[N + 1];
        w = new int[N + 1];
        s = new int[N + 1];
        dp = new int[V + 1];  // dp[j]：容量j时的最大价值
        g = new int[V + 1];   // 临时数组，保存上一轮dp状态

        // 读取每个物品的信息
        for (int i = 1; i <= N; i++) {
            v[i] = sc.nextInt();  // 体积
            w[i] = sc.nextInt();  // 价值
            s[i] = sc.nextInt();  // 数量限制
        }

        // 动态规划主循环：遍历每个物品
        for (int i = 1; i <= N; i++) {
            // 保存上一轮dp状态到g数组（用于单调队列比较）
            System.arraycopy(dp, 0, g, 0, V + 1);

            // 按余数分组：对每个余数mod（0到v[i]-1）分别处理
            for (int mod = 0; mod < v[i]; mod++) {
                // 单调队列：维护窗口内的最优决策
                Deque<Integer> deque = new ArrayDeque<>();

                // 遍历当前余数组内的所有容量j（步长为v[i]）
                for (int j = mod; j <= V; j += v[i]) {
                    
                    // 步骤1：维护队列窗口大小，移除超出数量限制的决策
                    // 窗口大小限制：最多选择s[i]件物品
                    while (!deque.isEmpty() && 
                           (j - deque.peekFirst()) / v[i] > s[i]) {
                        deque.pollFirst();  // 移除队首过期决策
                    }

                    // 步骤2：计算当前决策的相对价值（用于单调性比较）
                    // 公式：val = g[j] - (j/v[i]) * w[i]
                    // 目的：消除物品数量对价值比较的影响
                    int val = g[j] - (j / v[i]) * w[i];

                    // 步骤3：维护队列单调递减性
                    // 移除队尾价值小于等于当前决策的决策
                    while (!deque.isEmpty() && 
                           (g[deque.peekLast()] - (deque.peekLast() / v[i]) * w[i]) <= val) {
                        deque.pollLast();
                    }

                    // 步骤4：将当前决策加入队列
                    deque.offerLast(j);

                    // 步骤5：更新dp[j]为队列中最优决策对应的价值
                    int bestIndex = deque.peekFirst();  // 队首为当前窗口最优决策
                    dp[j] = g[bestIndex] + ((j - bestIndex) / v[i]) * w[i];
                }
            }
        }

        // 在所有容量中寻找最大价值
        int ans = 0;
        for (int i = 0; i <= V; i++) {
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}

📊 复杂度分析

指标	复杂度	说明
时间复杂度	O(N × V)	每个物品处理V个容量，共N个物品
空间复杂度	O(V)	使用一维dp数组，大小为V+1

🔄 算法执行流程

开始
  ↓
读取输入数据 (N, V, v[i], w[i], s[i])
  ↓
初始化dp数组为0
  ↓
遍历每个物品 i = 1 → N
  ↓
  保存dp状态到临时数组g
  ↓
  按余数分组 mod = 0 → v[i]-1
  ↓
    初始化单调队列deque
    ↓
    遍历容量 j = mod → V (步长v[i])
    ↓
      维护队列窗口大小（移除过期决策）
      ↓
      计算当前决策的相对价值
      ↓
      维护队列单调性
      ↓
      将当前决策加入队列
      ↓
      更新dp[j]为队列最优决策
  ↓
遍历结束，输出最大价值
结束

💡 关键点总结

🎯 算法核心

状态定义：dp[j] 表示容量j时的最大价值
优化思想：按余数分组 + 单调队列维护最优决策
时间复杂度：从O(N×V×S)优化到O(N×V)

🔧 实现技巧

余数分组：将容量按物品体积取模分组，分别处理
单调队列：维护窗口内的最优决策，保证O(1)获取最大值
相对价值：消除物品数量对价值比较的影响
窗口限制：通过队列大小控制物品选择数量

📈 性能对比

算法	时间复杂度	适用场景
朴素多重背包	O(N×V×S)	小规模数据
二进制优化	O(N×V×logS)	中等规模
单调队列优化	O(N×V)	大规模数据

🚀 应用建议

竞赛场景：优先掌握单调队列优化版本
工程实践：根据数据规模选择合适的算法
学习路径：先掌握0-1背包 → 完全背包 → 多重背包

🌟 总结

多重背包问题是动态规划在组合优化中的重要应用。通过单调队列优化，我们成功将时间复杂度从O(N×V×S)降低到O(N×V)，解决了大规模数据下的性能问题。

掌握要点：

✅ 理解按余数分组的优化思想
✅ 掌握单调队列的维护和使用
✅ 能够推导状态转移方程
✅ 熟悉算法的时间空间复杂度