捡贝壳问题

描述

小悦很喜欢收藏贝壳，幸运的是她生活在海边的一座美丽城市，有一天，她去到海边，看到有好多好多的贝壳。于是她决定要在时间t内要拣出价值为v的贝壳.
现在的问题时如何帮助小悦分析怎么才能拣出价值最大的v呢

输入描述

第一行有两个整数 T(1 <= T <= 1000) 和M(1<= M <= 100),用一个空格隔开,T代表总共能够用来

捡贝壳的时间，M代表贝壳的数目。接下来M行包括两个在1到100之间（包括1和100）的整数，分别表

示捡这个贝壳的时间和这个贝壳的价值。

输出描述

输出包括一行，这一行知包含一个整数，表示在规定的时间内，可以捡到的贝壳的最大价值。

用例输入 1 

70 3
71 100
69 1
1 2

用例输出 1 

3

//典型贪心
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int dp[101][1001]={0};
    int t,n;
    cin>>t>>n;
    int time[n+1]={0},value[n+1]={0};
    for (int i=1;i<=n;i++) cin>>time[i]>>value[i];
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=t;j++)
        {
            if (time[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-time[i]]+value[i]);
            else (dp[i][j]=dp[i-1][j]);
        }
    }
    cout<<dp[n][t];
}