这里公式是w[i-1][j-v[i]]+v[i]

import java.util.Scanner;



public class 装箱问题 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int m=sc.nextInt();//容量
		int n=sc.nextInt();//物品
		int[] v=new int[n+1];
		int[][] w=new int[n+1][m+1];
		for (int i = 1; i <= n; i++) {
			v[i]=sc.nextInt();
		}
		for (int i = 1; i <= n ; i++) {//物品
			for (int j = 1; j <= m ; j++) {//背包容量
				if (v[i]<=j) {
					//w[i-1][j-v[i]]+v[i]  
					//w[i-1][j-v[i]]上个物品放进去之后 还剩下多少容量
					//w[i-1][j-v[i]]+v[i] 剩下的容量加上 当前物品的容量
					w[i][j]=Math.max(w[i-1][j], w[i-1][j-v[i]]+v[i]);
				}else {
					w[i][j]=w[i-1][j];
				}
				

			}
		}
		System.out.println(m-w[n][m]);

	}

}

解题思路:

注意事项:

参考代码: