EOJ(动态规划）——1113. 装箱问题

单测试点时限: 2.0 秒

内存限制: 256 MB

有一个箱子容量为 V （正整数，0≤V≤20000），同时有 n 个物品（0<n≤30），每个物品有一个体积（正整数）。要求从 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入
输入有多组测试数据，第一行一个正整数 V, 表示箱子的容量

第二行一个数据 n 表示物品个数。

第三行有 n 个数据，描述每个物品的体积

输出
每个输出占一行，输出箱子最后剩下的最小体积

样例
input
24 一个整数，表示箱子容量
6 一个整数，表示有n个物品
8 3 12 7 9 7分别表示这n个物品的各自体积
output
0 一个整数，表示箱子剩余空间
hint:汉字是不需要处理的，只是为了描述题目

题目大意：

给n个有独立体积的物品，放入总体积为V的箱子中，问箱子最后剩下的最小体积多少。

题目解析：

同样是01背包问题。

具体代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 35
int weight[MAXN];
int dp[MAXN][20005];//dp[i][j]表示前i件物品放入空间为j所占据的最大空间
int main() {
	int V,n;
	while(cin>>V>>n) {
		for(int i=1; i<=n; i++)
			cin>>weight[i];
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=V; j++) {
				if(weight[i]>j)
					dp[i][j]=dp[i-1][j];
				else {
					dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+weight[i]);
				}
			}
		}
		cout<<V-dp[n][V]<<endl;
	}
	return 0;
}