装箱问题 (Java代码）

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int M=sc.nextInt();
		int N=sc.nextInt();
		int[]dp=new int[M+1];
		for (int i = 0; i < N; i++) {
			int w=sc.nextInt();
			int v=w;
			int s=1;
			for (int j = 1; j <=s; s-=j,j*=2)   {
				for (int k = M; k >=j*w; k--) {
					dp[k]=Math.max(dp[k], dp[k-j*w]+j*v);
				}
			}
			if(s>0){
				for (int k = M; k >=s*w; k--) {
					dp[k]=Math.max(dp[k], dp[k-s*w]+s*v);
				}
			}
		}
		System.out.println(M-dp[M]);
	}
}