题目描述：
约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草． 顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，
他最多可以运回多少体积的干草呢？
输入：
第一行两个整数，分别为 C 和 H。
第 2..H+1行：每一行一个整数代表第 i捆稻草的体积 Vi。
输出：
一个整数，为约翰能买到的稻草的体积。
输出时每行末尾的多余空格，不影响答案正确性
样例输入：
7 3
2 6 5
样例输出：
7
AC Code：
#include<bits/stdc++.h> using namespace std; #define N 50001 int dp[N],v[N]; int main() { int c,h; cin>>c>>h; for(int i=1;i<=h;i++) cin>>v[i]; memset(dp,0,sizeof(dp)); for(int i=1;i<=h;i++) { for(int j=c;j>=v[i];j--) { dp[j]=max(dp[j],dp[j-v[i]]+v[i]); } if(dp[c]==c)//如果此时已经装满马车，则直接输出。 { cout<<c; return 0;//没有这个if判断就会RE } } cout<<dp[c]<<endl; return 0; }
