题解 | [NOIP2001]装箱问题

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[] volumes = new int[n];
        for (int i = 0; i < n; i++) {
            volumes[i] = scanner.nextInt();
        }

        boolean[] dp = new boolean[V + 1];
        dp[0] = true;

        for (int v : volumes) {
            for (int i = V; i >= v; i--) {
                if (dp[i - v]) {
                    dp[i] = true;
                }
            }
        }

        int maxSum = 0;
        for (int i = V; i >= 0; i--) {
            if (dp[i]) {
                maxSum = i;
                break;
            }
        }

        System.out.println(V - maxSum);
    }
}

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

思路：

1. 输入处理：读取箱子容量V、物品个数n以及每个物品的体积。
2. 动态规划数组初始化：dp数组的大小为V+1，初始时只有dp[0]为true。
3. 状态转移：对于每个物品的体积，逆序遍历可能的容量，更新dp数组，确保每个物品只被考虑一次。
4. 寻找最大体积和：从V开始向下遍历，找到最大的i使得dp[i]为true，计算并输出剩余空间V - i。