链接：https://ac.nowcoder.com/acm/contest/24213/1017
来源：牛客网

题目描述

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

输入描述: 

1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积

输出描述: 

1个整数，表示箱子剩余空间。

题型：

动态规划--求最大值+选或不选问题

思路：

1.明确总问题：求最小剩余空间-->求总体积-最大体积-->需要求出不超过总体积的最大体积
2.明确子问题：求当已经选择了i个物品时，总体积为j
3.明确dp含义：可以设dp[i][j]为选择了i个物品时，总体积为j的状态是否存在，如果存在，则为1，如果不存在，则为0，所以不超过总体积的最大体积的值即为i从V开始，一直到0，dp[n][i]最先为1时的i的值
4.明确状态转移方程：当j<a[i]时，有dp[i][j]=dp[i-1][j]，当j>=a[i]时，有dp[i][j]=dp[i-1][j]||dp[i-1][j-a[i]];
5.明确初始化：dp[0][0]=1,表示什么都不选时体积为0的状态是存在的
6.明确i和j的范围：i:1~n    j:0~V（注意j不是1~V，j=0也要考虑）

代码（二维数组）： 

#include<bits/stdc++.h>
using namespace std;
int dp[32][20200],a[32];
int main(){
	int n,V,maxn=0;
	scanf("%d%d",&V,&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=V;j++){
			if(j<a[i]) dp[i][j]=dp[i-1][j];
			else dp[i][j]=dp[i-1][j]||dp[i-1][j-a[i]];
		}
	}
	for(int i=V;i>=0;i--){
		if(dp[n][i]){
			maxn=i;
			break;
		}
	}
	printf("%d\n",V-maxn);
	return 0;
}

当然，这个二维数组可以压缩成一维（因为第i行的状态只跟第i-1行的状态有关），注意压缩之后j要反着取，并且j的范围改成V~a[i]（因为a[i]前的状态不需要改，直接继承之前的状态就行了）

代码（一维数组）： 

#include<bits/stdc++.h>
using namespace std;
int dp[20200],a[32];
int main(){
	int n,V,maxn=0;
	scanf("%d%d",&V,&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=V;j>=a[i];j--){
			dp[j]=dp[j]||dp[j-a[i]];
		}
	}
	for(int i=V;i>=0;i--){
		if(dp[i]){
			maxn=i;
			break;
		}
	}
	printf("%d\n",V-maxn);
	return 0;
}