题目链接

【模板】完全背包

题目描述

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

输入:

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

输出:

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

解题思路

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

  1. 状态定义:

    • 我们定义一个一维数组 ，其中 表示背包容量为 时，可以获得的最大总价值。

  2. 状态转移:

    • 对于第 种物品（体积为 ，价值为 ），我们可以选择不放或者放一个或多个。
    • 状态转移方程为：
    • 这个方程的含义是，对于当前容量 ，我们可以选择不放入第 种物品，此时最大价值就是 （由前 种物品决定）；或者选择放入第 种物品，此时背包的剩余容量为 ，最大价值为 。我们在这两种选择中取最大值。

  3. 遍历顺序:

    • 遍历物品是外层循环，遍历背包容量是内层循环。
    • 与01背包的关键区别在于，内层循环（背包容量）必须是正序遍历（从 到 ）。
    • 为什么要正序遍历？因为 在计算 时，应该是已经考虑过第 种物品之后的值。这样就相当于允许第 种物品被重复选取。如果逆序遍历，那么在计算 时， 还是只考虑了前 种物品的状态，这就变成了01背包问题。

  4. 初始化:

    • 我们需要将 数组全部初始化为0，因为在不放任何物品时，价值为0。

最终， 就是我们要求的答案。

代码

#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])

算法及复杂度

  • 算法：动态规划（完全背包）
  • 时间复杂度： - 其中 是测试数据组数， 是物品数量， 是背包容量。
  • 空间复杂度： - 主要开销是 数组。