蒜头君去超市购物，他有一只容量为 V 的购物袋，同时他买了 n件物品，已知每件物品的体积 vi。蒜头君想知道，挑选哪些物品放入购物袋中，可以使袋子剩余的空间最小。
输入格式
第一行输入一个整数 V（1≤V≤20,000），表示购物袋的容量。
第二行输入一个整数 n（1≤n≤30），表示蒜头君购买的 n 件物品。
接下来输入 n 行，每行输入一个整数 vi（1≤vi≤10,000），表示第 i 件物品的体积。
输出格式
输出一行，输出一个整数，表示购物袋最小的剩余空间。
样例输入
20
5
7
5
7
3
7
样例输出
1
解题思路：
本题与普通动态规划有些不同，多了一个袋子的范围v。
因此我们可以根据袋子的体积和物体的编号来确定状态。
于是我们使dpi代表在第1~i编号中j容量的袋子可放下最大物品体积。
我们把问题分层，第i号物体放，还是不放。（令shop[i]为第i个物体的体积）
当j
当j>=shop[i]时，可以放，也可以不放。
可以：dp[i][j]=dp[i-1][j-shop[i]]+shop[i]//放进去了，袋子所剩的容量能在1~i-1中选择其最大的物体
不放：dp[i][j]=dp[i-1][j]
则dp[i][j]=max(dp[i-1][j-shop[i]]+shop[I],dp[i-1][j]) //选择较大的
最好下标从1开始，初始dpall={0}，这样，初始值就无需设置了。
#include<iostream>
#include<algorithm>
using namespace std;
int dp[31][20001];//全局变量，默认都是0
int main(){
int v,n;
cin>>v>>n;
int shop[31];
for(int i=1;i<=n;i++) cin>>shop[i];//录入物体体积
for(int i=1;i<=n;i++){
for(int j=1;j<=v;j++){
if(shop[i]>j)
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j-shop[i]]+shop[i],dp[i-1][j]);
}
}
cout<<v-dp[n][v];//输出最后所剩下的体积
}
