题解 | #【模板】完全背包#

题目链接

【模板】完全背包

题目描述

有 $n$ 种物品和一个容量为 $m$ 的背包。第 $i$ 种物品的体积是 $w_i$ ，价值是 $v_i$ 。每种物品都有无限件可用。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

1. 状态定义 我们使用一个一维数组 $dp$ 来进行状态表示。 $dp[j]$ 的含义是：当背包容量为 $j$ 时，能获得的最大总价值。我们的最终目标就是求解 $dp[m]$ 。

2. 状态转移方程 我们依次遍历每一种物品，并用它来更新 $dp$ 数组。对于第 $i$ 种物品（体积为 $w_i$ ，价值为 $v_i$ ），当我们考虑如何填充容量为 $j$ 的背包时，存在两种决策：

不放入物品 $i$ ：这种情况下，背包的价值就是只考虑前 $i-1$ 种物品时的价值，即更新前的 $dp[j]$ 。
放入物品 $i$ ：这种情况下，我们必然在背包中放入了至少一个物品 $i$ ，占用了 $w_i$ 的体积，获得了 $v_i$ 的价值。背包的剩余容量为 $j-w_i$ ，这部分剩余容量可以用来装入任意物品（包括继续装物品 $i$ ）。因此，这种情况下的最大价值为 $dp[j-w_i] + v_i$ 。

综合以上两种情况，状态转移方程为： $dp[j] = \max(dp[j], dp[j - w_i] + v_i)$

3. 与0-1背包的关键区别：循环顺序 这个状态转移方程在形式上与0-1背包完全相同。它们唯一的区别在于内层循环（遍历背包容量 $j$ ）的顺序。

在0-1背包中，为保证每个物品只被选择一次， $dp[j-w_i]$ 必须是上一轮循环（即不包含物品 $i$ ）的状态。因此，内层循环需要逆序遍历（从 $m$ 到 $w_i$ ）。
在完全背包中，因为物品可以被选择多次，所以当我们计算 $dp[j]$ 时，我们希望 $dp[j-w_i]$ 是本轮循环中已经更新过的状态（即已经包含了物品 $i$ 的最优解）。要实现这一点，内层循环必须正序遍历（从 $w_i$ 到 $m$ ）。这样，在计算 $dp[j]$ 时， $dp[j-w_i]$ 可能已经被物品 $i$ 更新过，这恰好体现了物品 $i$ 可以被重复选择的特性。

关于Python超时的说明 本题的总计算量在最坏情况下可达 $T \cdot n \cdot m \approx 2 \cdot 10^8$ 。这个计算量对于 C++ 和 Java 通常是可以接受的，但对于标准 Python (CPython) 解释器来说，往往会因为执行效率问题而超时。因此，下面提供的 Python 代码虽然在算法上是正确的，但可能无法通过所有测试点。

算法总结

初始化一个大小为 $m+1$ 的 $dp$ 数组，所有元素为0。
外层循环遍历每种物品 $i$ 。
内层循环正序遍历背包容量 $j$ ，从 $w_i$ 到 $m$ 。
应用状态转移方程更新 $dp[j]$ 。
所有循环结束后， $dp[m]$ 即为答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> w(n);
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i] >> v[i];
    }

    vector<long long> dp(m + 1, 0);

    for (int i = 0; i < n; ++i) {
        for (int j = w[i]; j <= m; ++j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[m] << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        long[] dp = new long[m + 1];
        
        for (int i = 0; i < n; i++) {
            for (int j = w[i]; j <= m; j++) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }

        System.out.println(dp[m]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

def solve():
    line = sys.stdin.readline()
    if not line.strip():
        return
    n, m = map(int, line.split())
    
    items = []
    for _ in range(n):
        items.append(list(map(int, sys.stdin.readline().split())))

    dp = [0] * (m + 1)

    for w, v in items:
        for j in range(w, m + 1):
            dp[j] = max(dp[j], dp[j - w] + v)

    print(dp[m])

def main():
    t_str = sys.stdin.readline()
    if not t_str.strip():
        return
    t = int(t_str)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：动态规划（完全背包问题）。
时间复杂度： $O(T \cdot n \cdot m)$ ，其中 $T$ 是测试数据组数， $n$ 是物品数量， $m$ 是背包容量。
空间复杂度： $O(n+m)$ 。对于每组测试数据，需要 $O(n)$ 的空间存储 $n$ 个物品的体积和价值，以及 $O(m)$ 的空间存储DP状态数组。