题解 1660: 蓝桥杯算法训练VIP-装箱问题

参考代码:

import java.util.Scanner;


public class 装箱问题 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//题目 1660: [蓝桥杯][算法训练VIP]装箱问题
		Scanner scanner=new Scanner(System.in);
		int m=scanner.nextInt();//箱子大小
		int n=scanner.nextInt();//物品数量
		int [] dp=new int [m+1];
		for (int i = 1; i <=n; i++) {
			//输入物品价值
			int v=scanner.nextInt();
			for (int j = m; j >=v; j--) {
				dp[j]=Math.max(dp[j], dp[j-v]+v);
			}
		}
	    System.out.println(m-dp[m]);
		
		
	}

}