描述 Description
约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为 C(1≤C≤50000) 个单位的马车，去顿因家买一些干草． 顿因有 H(1≤H≤5000) 包干草，每一包都有它的体积 Vi(l≤Vi≤C).
约翰只能整包购买，他最多可以运回多少体积的干草呢？
输入格式 InputFormat
第 1 行输入 C 和 H，之后 H 行一行输入一个 Vi．
输出格式 OutputFormat
最多的可买干草体积．
样例输入 SampleInput
7 3
2
6
5
样例输出 SampleOutput
7
数据范围和注释 Hint
The wagon holds 7 volumetric units; three bales are offered for sale with volumes of 2, 6, and 5 units, respectively.
Buying the two smaller bales fills the wagon.
来源 Source
Silver
BZOJ 1606 ***
代码 Code
水。简单的 01 背包。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int f[50005];
int v[50005];
int i,j,t,n,m,c,h,l,r,k,z,y,x,ans;
int main()
{
scanf("%d%d",&c,&h);
for (i=1;i<=h;i++) scanf("%d",&v[i]);
for (i=1;i<=h;i++) for (j=c;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+v[i]);
ans=max(ans,f[j]);
}
printf("%d",ans);
return 0;
}