题解 | 【模板】01背包

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int V = scanner.nextInt();
        int[][] items = new int[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = scanner.nextInt();
            items[i][1] = scanner.nextInt();
        }
        
        int[] dp1 = new int[V + 1];
        Arrays.fill(dp1, 0);
        for (int i = 0; i < n; i++) {
            int vi = items[i][0];
            int wi = items[i][1];
            for (int j = V; j >= vi; j--) {
                if (dp1[j - vi] + wi > dp1[j]) {
                    dp1[j] = dp1[j - vi] + wi;
                }
            }
        }
        int ans1 = dp1[V];
        
        int[] dp2 = new int[V + 1];
        Arrays.fill(dp2, Integer.MIN_VALUE);
        dp2[0] = 0;
        for (int i = 0; i < n; i++) {
            int vi = items[i][0];
            int wi = items[i][1];
            for (int j = V; j >= vi; j--) {
                if (dp2[j - vi] != Integer.MIN_VALUE) {
                    if (dp2[j - vi] + wi > dp2[j]) {
                        dp2[j] = dp2[j - vi] + wi;
                    }
                }
            }
        }
        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。读取每个物品的体积和价值，存储在二维数组 items 中。
2. 普通背包问题处理：初始化 dp1 数组，所有元素为0。对每个物品，逆序遍历背包容量，更新 dp1 数组，确保每个物品只被选中一次。
3. 恰好装满的背包问题处理：初始化 dp2 数组，dp2[0] 为0，其余为负无穷。对每个物品，逆序遍历背包容量，仅在合法时更新当前状态。
4. 结果输出：输出普通背包问题的最大价值 ans1。输出恰好装满时的最大价值 ans2，若无法恰好装满则输出0。