题解 | #装箱问题#

二维dp：横向是背包剩余容量，纵向是第几个物品
dp值是能否填到这个容量
简化成一维空间，倒着往前推

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		int V = nextInt();
		int n = nextInt();
		int[] list = new int[n];
		for (int i = 0; i < list.length; i++)
			list[i] = nextInt();
		boolean[] dp = new boolean[V+1];
		dp[0] = true;
		for (int i = 0; i < n; i++) {
			for (int j = V; j >= 0; j--) {
				if(j-list[i] < 0) break;
				if(dp[j-list[i]])
					dp[j] = true;
			}
		}
		for (int i = V; i >= 0; i--) {
			if(dp[i]) {
				System.out.println(V-i);
				return;
			}
		}
	}

	
	
	
	
	static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StreamTokenizer st = new StreamTokenizer(br);
	static int nextInt() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
	static long nextLong() throws IOException {
		st.nextToken();
		return (long)st.nval;
	}
}