欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1049 装箱问题

程序员文章站 2022-07-16 10:18:18
...

题目链接: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;
}

相关标签: 背包dp