Java题解:01背包问题

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int v = scanner.nextInt(); // 箱子容量

        int n = scanner.nextInt(); // 物品数量

        int[] vol = new int[n + 1];

        for (int i = 1; i <= n; i++) {

            vol[i] = scanner.nextInt(); // 物品体积

        }

        int[][] dp = new int[n + 1][v + 1];

        for (int i = 1; i <= n; i++) {

            for (int j = 0; j <= v; j++) {

                dp[i][j] = dp[i - 1][j]; // 不装入第i个物品

                if (j >= vol[i]) { // 考虑装入第i个物品

                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - vol[i]] + vol[i]);

                }

            }

        }

        System.out.println(v - dp[n][v]); // 输出箱子剩余空间

    }

}