Codevs 5564 陶陶摘苹果2

5564 陶陶摘苹果2

时间限制: 1 s　　　　空间限制: 16000 KB　　　　题目等级 : 白银 Silver 

题目描述 Description

陶陶已经够高摘到所有苹果了，但是他力量有限，最大承受质量为Q kg，有K个苹果，每个苹果有自己的价值和质量，请你帮陶陶看看怎么摘能够价值最大。

输入描述 Input Description

两个整数Q，K，代表最大承受，苹果的数量。

以下k行，两个整数w，v，代表每个苹果的质量和价值。

输出描述 Output Description

输出一个整数代表最大的收益。

样例输入 Sample Input

10  3

5  20

3  15

8  29

 

样例输出 Sample Output

35

 

数据范围及提示 Data Size & Hint

 对于100%的数据  Q≤100  K≤1000  V，W≤100

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int m,n,w[1005],v[1005],f[105];
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
      scanf("%d%d",&w[i],&v[i]);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }  
    printf("%d",f[m]);
    return 0;
}