洛谷 P1049 [NOIP2001 普及组] 装箱问题题解

 本题要求的是一个物品最多放一次，所以是01背包问题，题目要求最少的剩余空间。可以转化成最多能装多少，最后输出是减去即可。

#include
using namespace std;
using ll = long long;
const int N = 2e4 + 9;
ll dp[N], v[N];
 
void solve()
{
	ll V, n; cin >> V >> n;
	for (int i = 1; i <= n; ++i) cin >> v[i];
	for (int i = 1; i <= n; ++i)
	{
		for (int j = V; j >= v[i]; --j)
		{
			dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
		}
	}
 
	cout << V - dp[V];
}
 
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}