AcWing 4. 多重背包问题 I

◎

本节目标

在每种物品数量有限时直接枚举可取次数，建立多重背包基线。

返回背包模型框架

查看 AcWing 原题

题意与约束

每种物品 (v,w,s) 的体积、价值、数量上限分别为 v、w、s，求容量 m 内最大价值。

第一反应与重复子问题

每类物品的可取数是 0..s，直接枚举所有分配仍会组合爆炸；处理到某类、某容量时的最优前缀可复用。

状态定义与转移推导

dp[j] 表示处理完前几类物品的最大价值。对当前 (v,w,s)，倒序容量，并枚举 count=1..s：dp[j]=max(dp[j],dp[j-count·v]+count·w)。

正确性依据

倒序确保来源状态尚未使用当前类物品；再枚举合法数量，覆盖该类取零到 s 件的所有可能，数量上限不会丢失。

样例执行过程

单类 (2,3,2)、容量 6 时最多拿两件，答案 6 而不是完全背包会得到的 9。

代码实现

C++

C++17

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

int maxValue(int m, const vector<tuple<int, int, int>>& items) {
    vector<int> dp(m + 1, 0);
    for (auto [v, w, s] : items) {
        for (int j = m; j >= v; j--) {
            for (int count = 1; count <= s && count * v <= j; count++) {
                dp[j] = max(dp[j], dp[j - count * v] + count * w);
            }
        }
    }
    return dp[m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> items(n);
    for (auto& [v, w, s] : items) {
        cin >> v >> w >> s;
    }
    cout << maxValue(m, items) << '\n';
    return 0;
}

Python

Python 3

import sys


def max_value(m: int, items: list[tuple[int, int, int]]) -> int:
    dp = [0] * (m + 1)
    for v, w, s in items:
        for capacity in range(m, v - 1, -1):
            for count in range(1, s + 1):
                if count * v > capacity:
                    break
                dp[capacity] = max(dp[capacity], dp[capacity - count * v] + count * w)
    return dp[m]


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[0], data[1]
    items = [(data[i], data[i + 1], data[i + 2]) for i in range(2, 2 + 3 * n, 3)]
    print(max_value(m, items))


if __name__ == '__main__':
    main()

复杂度分析

时间 O(m Σs)，空间 O(m)。

边界与易错点

• 不能忽略 s，否则变成完全背包。
• count·v 不能超过当前容量。
• 仍以 (v,w,s) 固定字段顺序。

模式迁移

当数量上限较大时可进一步学习二进制拆分；本题先用直接枚举验证有限次数语义。