2140: 信息学奥赛一本通T1295-装箱问题

解题思路:经典01背包

注意事项:容积倒序

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e4 + 10;
int f[N],w[N],v, n;
int main()
{
	cin >> v >> n;
	for(int i = 1; i <= n; i ++) cin >> w[i];
	for(int i = 1; i <= n; i ++)
		for(int j = v; j >= w[i]; j --)
			f[j] = max(f[j], f[j- w[i]] + w[i]);
			
	cout << v - f[v];
	return 0;
}