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

总结：
本题使用动态规划

import java.util.*;
public class Main{
    public static void main(String arg[]){
        Scanner sc = new Scanner(System.in);
        int vol = sc.nextInt();//箱子容量
        int num = sc.nextInt();//物品数量
        int[] v = new int[num+1];//物品的体积
        for(int i=1;i<=num;i++)
            v[i] = sc.nextInt();
        int[] dp = new int[vol+1];//记录可装入箱中的最大体积
        for(int i=1;i<=num;i++){
            //每个物品只能使用一次，故使用倒叙
            for(int j=vol;j>=v[i];j--){
                dp[j] = Math.max(dp[j],dp[j-v[i]]+v[i]);
            }
        }
        System.out.println(vol-dp[vol]);
    }
}