题解 | 【模板】完全背包

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int V = scanner.nextInt();
        List<int[]> items = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            items.add(new int[]{v, w});
        }

        int[] dp1 = new int[V + 1];
        Arrays.fill(dp1, 0);
        for (int[] item : items) {
            int v = item[0];
            int w = item[1];
            for (int j = v; j <= V; j++) {
                if (dp1[j - v] + w > dp1[j]) {
                    dp1[j] = dp1[j - v] + w;
                }
            }
        }
        int ans1 = dp1[V];
        int[] dp2 = new int[V + 1];
        Arrays.fill(dp2, Integer.MIN_VALUE);
        dp2[0] = 0;
        for (int[] item : items) {
            int v = item[0];
            int w = item[1];
            for (int j = v; j <= V; j++) {
                if (dp2[j - v] != Integer.MIN_VALUE) {
                    dp2[j] = Math.max(dp2[j], dp2[j - v] + w);
                }
            }
        }
        int ans2 = dp2[V] == Integer.MIN_VALUE ? 0 : dp2[V];

        System.out.println(ans1);
        System.out.println(ans2);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取物品数量n和背包体积V，以及每个物品的体积和价值，存储在列表中。
2. 普通完全背包问题：初始化dp1数组为0，表示每个体积可以装的最大价值初始为0。遍历每个物品，更新每个体积的最大价值。对于每个物品的体积v和价值w，从体积v开始到V，更新可能的更大价值。
3. 恰好装满的完全背包问题：初始化dp2数组为负无穷，表示不可达状态，只有dp2[0]为0，表示恰好装满体积0的价值为0。同样遍历每个物品，但只有在当前体积减去物品体积的状态可达时，才更新当前状态。
4. 输出结果：分别输出普通背包问题和恰好装满背包问题的最大价值结果。