#include <iostream>
#include <algorithm>
using namespace std;

int V, n;
bool dp[35][20005] = {0}; // dp[x][V]用前x个物品是否可以凑出V的空间
int weights[35] = {0};

int main() {
	cin >> V >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> weights[i];
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= V; ++j) {
			if (dp[i-1][j] == 1) {
				dp[i][j] = 1;
				if(j+weights[i] <= V)dp[i][j+weights[i]] = 1;
				
			}
		}
	}
	int max = 0;
	for (int j = 0; j <= V; ++j) {
		if (dp[n][j]==1) {
			if (j > max) max=j;
			//cout << "V " << j << endl;
		}
	}
	cout << V-max << endl;
}

这段动态规划的代码是可以AC的（虽然看着不是那么好看），但令我疑惑的是，if(j+weights[i] <= V)dp[i][j+weights[i]] = 1;这一行代码中，如果把if语句判断的条件去掉，允许在j+weights[i]大于箱子体积的情况下继续递推，结果是会出问题的，#5测试点会输出0，直接WA。

可是我怎么也想不明白，如果j+weights[i]>V,在求最终结果的时候，我会始终让指针小于V的值，根本就用不上V列之后的情况，按说上文这么做是对结果没有影响的呀？

dp[x][y]数组的作用是，在前x个东西中能否凑出体积y。