AcWing 3. 完全背包问题

◎

本节目标

用容量正序的一维动态规划处理每件物品可重复选择的最大价值问题。

返回背包模型框架

查看 AcWing 原题

题意与约束

每种物品 (v, w) 可以选任意次，在容量不超过 m 时最大化总价值。

第一反应与重复子问题

若枚举每种物品拿几件，选择数随容量增长。处理到某种物品、剩余容量相同的子问题会反复出现。

状态定义与转移推导

令 dp[j] 为容量 j 内最大价值。选一件当前物品后仍可选它，因此 dp[j]=max(dp[j], dp[j-v]+w) 中的 dp[j-v] 应属于当前物品层。

正确性依据

容量正序时 j-v 已在本轮更新，正好表示已经使用零件或多件当前物品后的最优值；不选分支保留原 dp[j]。

样例执行过程

单件 (2,3)、容量 6 时，dp[2]=3、dp[4]=6、dp[6]=9，正序让同一种物品连续参与转移。

代码实现

C++

C++17

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

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

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

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

Python

Python 3

import sys


def max_value(m: int, items: list[tuple[int, int]]) -> int:
    dp = [0] * (m + 1)
    for v, w in items:
        for j in range(v, m + 1):
            dp[j] = max(dp[j], dp[j - v] + 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]) for i in range(2, 2 + 2 * n, 2)]
    print(max_value(m, items))


if __name__ == '__main__':
    main()

复杂度分析

时间 O(nm)，空间 O(m)。

边界与易错点

• 容量不足时不更新。
• 写成倒序会退化为每件最多一次的 01 背包。
• (v, w) 固定表示体积、价值。

模式迁移

若目标改为最少数量或方案数，保留正序的可重复语义，再替换状态值和初始值。