动态规划 专题

洛谷 P1049 装箱问题

题目描述

输入输出格式

说明

NOIP 2001普及组 第4题

时空限制

  • 时间：1000ms
  • 空间：128MB

思路

这题也比较基础，直接上递推公式。

dp[j] = max(dp[j], dp[j-good[i]]+good[i]);
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int dp[100000];
int good[100000];

int main(){
	int v,n;
	memset(good,0,sizeof(good));
	scanf("%d%d",&v,&n);
	for(int i = 1; i <= n; ++i){
		scanf("%d",&good[i]);
	}
	for(int i = 1; i <= n; ++i){
		for(int j = v; j >= 0; --j){
			if(j >= good[i]){
				dp[j] = max(dp[j], dp[j-good[i]]+good[i]);
			}
		}
	}
	printf("%d", v-dp[v]);
	return 0;
}