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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //动态规划问题
	    //总共的容量
        int total=in.nextInt();
        //物体放入的数量
        int n=in.nextInt();
        //将物体质量放入集合中方便遍历
        int arr[]=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=in.nextInt();
        }
        //定义一个比盒子大的数组，用来保持每次循环后最大的值，+1是为了方便取到最后的值
        int[] dp=new int[total+1];
        //对集合进行遍历，每次都可以拿到一个物品放入后的最大值
        for(int i=0;i<n;i++){
            for(int j=total;j>=arr[i];j--){
                dp[j]=Math.max(dp[j],dp[j-arr[i]]+arr[i]);
            }
        } 
        //求剩余，就用总共的数量去减去最大的数量
        System.out.print(total-dp[total]);
    }
}