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

【模板】完全背包

https://www.nowcoder.com/practice/deda4293d9b24ce1aeaf1813c88b8c25

题目链接

【模板】完全背包

题目描述

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

输入:

第一行输入一个整数 $T$ ，表示有 $T$ 组测试数据。
对于每组测试数据：
- 第一行输入两个整数 $N, V$ ，分别表示物品数量和背包容量。
- 接下来 $N$ 行，每行输入两个整数 $v_i, w_i$ ，分别表示第 $i$ 件物品的体积和价值。

输出:

对于每组测试数据，输出一个整数，表示能获得的最大总价值。

解题思路

本题是典型的 完全背包问题 模型。与01背包问题不同的是，每种物品可以选取无限次。我们可以使用动态规划来解决。

状态定义:
- 我们定义一个一维数组 $dp$ ，其中 $dp[j]$ 表示背包容量为 $j$ 时，可以获得的最大总价值。
状态转移:
- 对于第 $i$ 种物品（体积为 $v_i$ ，价值为 $w_i$ ），我们可以选择不放或者放一个或多个。
- 状态转移方程为： $dp[j] = \max(dp[j], dp[j - v_i] + w_i)$
- 这个方程的含义是，对于当前容量 $j$ ，我们可以选择不放入第 $i$ 种物品，此时最大价值就是 $dp[j]$ （由前 $i-1$ 种物品决定）；或者选择放入第 $i$ 种物品，此时背包的剩余容量为 $j - v_i$ ，最大价值为 $dp[j - v_i] + w_i$ 。我们在这两种选择中取最大值。
遍历顺序:
- 遍历物品是外层循环，遍历背包容量是内层循环。
- 与01背包的关键区别在于，内层循环（背包容量）必须是正序遍历（从 $v_i$ 到 $V$ ）。
- 为什么要正序遍历？因为 $dp[j - v_i]$ 在计算 $dp[j]$ 时，应该是已经考虑过第 $i$ 种物品之后的值。这样就相当于允许第 $i$ 种物品被重复选取。如果逆序遍历，那么在计算 $dp[j]$ 时， $dp[j-v_i]$ 还是只考虑了前 $i-1$ 种物品的状态，这就变成了01背包问题。
初始化:
- 我们需要将 $dp$ 数组全部初始化为0，因为在不放任何物品时，价值为0。

最终， $dp[V]$ 就是我们要求的答案。

代码

c++
java
python

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

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, V;
        cin >> N >> V;
        vector<int> v(N), w(N);
        for (int i = 0; i < N; ++i) {
            cin >> v[i] >> w[i];
        }

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

        for (int i = 0; i < N; ++i) {
            for (int j = v[i]; j <= V; ++j) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        cout << dp[V] << "\n";
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int N = sc.nextInt();
            int V = sc.nextInt();
            int[] v = new int[N];
            int[] w = new int[N];
            for (int i = 0; i < N; i++) {
                v[i] = sc.nextInt();
                w[i] = sc.nextInt();
            }

            long[] dp = new long[V + 1];

            for (int i = 0; i < N; i++) {
                for (int j = v[i]; j <= V; j++) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }
            System.out.println(dp[V]);
        }
    }
}

T = int(input())
for _ in range(T):
    N, V = map(int, input().split())
    items = []
    for i in range(N):
        v, w = map(int, input().split())
        items.append((v, w))

    dp = [0] * (V + 1)

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

    print(dp[V])