题目描述 Description
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述 Input Description
一个整数v，表示箱子容量
一个整数n，表示有n个物品
接下来n个整数，分别表示这n 个物品的各自体积
输出描述 Output Description
一个整数，表示箱子剩余空间。
样例输入 Sample Input
24
6
8
3
12
7
9
7
样例输出 Sample Output
0
解题思路：
这几天打算开始撸dp了，先从code[vs]上最为简单的dp开始打吧，一道一道耐心写总结，写方法，慢慢体会，听知乎上说，没有100+的dp题，是根本不能理解dp的本质的，目前我只了解到了最为关键的几个地方，也就是我们常说的 状态和 状态转移方程，状态转移方程就是状态间转移的方程，NM，这不是废话么？哈哈，，所说的状态是子状态之间的转移了。而对于所有的dp问题，都可以归结为对于状态的定义和对于状态转移方程的求解了。
对于这道题我们定义的状态是：f[j]，表示加到第j件物品后的最大体积
状态转移方程：f[j] = max{ f[j],f[j-w[i]+w[i] };
代码：
# include<cstdio>
# include<iostream>
# include<cstring>
# include<algorithm>
using namespace std;
int w[33];
int f[20005];
int main(void)
{
int V,n;
cin>>V>>n;
memset(f,0,sizeof(f));
for( int i = 1;i <= n;i++ )
cin>>w[i];
for( int i = 1;i <= n;i++ )
{
for( int j = V;j >= w[i];j-- )
{
f[j]=max(f[j],f[j-w[i]]+w[i]);//f[j]表示装到第j个物的最大体积
}
}
cout<<V-f[V]<<endl;
return 0;
}