P1049 装箱问题

题目链接：P1049 装箱问题

01背包：

剩余空间最小->使用空间最大

#include<iostream>

using namespace std;

const int M = 20010,N = 40;

int n,m;
int f[M];
int v[N];

int main() {
	cin >> m >> n;
	for(int i = 1; i <= n; i ++ ) cin >> v[i];
	for(int i = 1; i <= n; i ++ ){
		for(int j = m; j >= v[i]; j --){
			f[j] = max(f[j],f[j - v[i]] + v[i]);
		}
	}
	cout<<m - f[m]<<endl;								
	return 0;
}