题解 | #[NOIP2001]装箱问题#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int V = Integer.valueOf(scan.nextLine().trim());
        int n = Integer.valueOf(scan.nextLine().trim());
        int[] vs = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            vs[i] = Integer.valueOf(scan.nextLine().trim());
        }
        int[] dp = new int[V + 1];
        for (int Goods = 1; Goods <= n; Goods++) {
            for (int Volume = V; Volume >= vs[Goods]; Volume--) {
                dp[Volume] = Math.max(dp[Volume], vs[Goods] + dp[Volume - vs[Goods]]);
            }
        }
        System.out.println(V - dp[V]);
    }
}