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

/**
 *  装箱子问题 - 动态规划求解
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int bagV = sc.nextInt();  // 箱子容量
            int goodsNums = sc.nextInt(); // 物品个数
            int[] goodsV = new int[goodsNums];  // 物品体积
            for (int i = 0; i < goodsNums; i++) {
                goodsV[i] = sc.nextInt();
            }
            
            // TODO dp[j] 表示可以装的最大空间
            int[] dp = new int[bagV + 1];

            for (int i = 0; i < goodsNums; i++) {
                // 每个物品只能使用1次，所以要倒叙遍历
                for (int j = bagV; j >= goodsV[i]; j--) {
                    dp[j] = Math.max(dp[j],dp[j-goodsV[i]] + goodsV[i]);
                }
            }
            // TODO babV - dp[j] 是剩余的空间
            System.out.println(bagV - dp[bagV]);

        }
    }

}