蓝桥杯算法训练VIP-装箱问题(背包同种思路)

import java.util.Scanner;

public class Main3 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();// 最大体积
		int n = in.nextInt();// 物品数
		int[] dp = new int[m+1];
		for (int i = 1; i <= n; i++) {
			int v = in.nextInt();// 物品体积
			for (int j = m; j >= v; j--) {
				dp[j] = Math.max(dp[j], dp[j - v] + v);
			}
		}
		System.out.println(m-dp[m]);
	}
}