背景

第一次在 AtCoder 上做到 01 背包，发现虽然是模板题，但自己写的时候还是卡了不少地方——主要是 Java 的数组类型和下标转换细节。

题目描述

给定 N 个物品，每个物品有重量 w[i] 和价值 v[i]。背包容量为 W，求能装入的最大总价值。

每个物品最多选一次，经典的 01 背包问题。

思路分析

01 背包的标准做法是用一维 DP 数组，容量从大到小遍历，保证每个物品只取一次。

转移方程：

1
f[j] = max(f[j - w[i]] + v[i], f[j])

其中 f[j] 表示容量为 j 时能获得的最大价值。

关键细节：

  • 数据范围较大，f 数组必须开 long，否则会溢出
  • Java 中数组下标必须是 int，而 w[i] 存为 long 时需要用 (int) 强转
  • 空间上提前初始化一个足够大的数组（如 maxn = 100005），避免动态扩容

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;

public class Y {
    static final int maxn = 100005;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        long[] f = new long[maxn];
        long[] w = new long[maxn];
        long[] v = new long[maxn];

        for (int i = 1; i <= n; ++i) {
            w[i] = scanner.nextLong();
            v[i] = scanner.nextLong();
        }

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

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

复杂度分析

  • 时间复杂度：O(N × W)，其中 N 为物品数，W 为背包容量
  • 空间复杂度：O(W)，使用一维滚动数组优化后的结果

小结

  • 01 背包的一维写法要倒序遍历容量，这是核心套路
  • Java 做题时注意 long 数组和 (int) 类型转换，各语言的类型细节不同容易在这里耽误时间
  • 初始化一个大数组而不是用 ArrayList 或动态结构，在竞赛中更省心