二维(AC)：
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N][N];  // f[i][j] : 前i株草药， 总时间为j的最大价值
int t[N], w[N];

int main()
{
    int T, M;
    cin >> T >> M;
    for(int i = 1 ; i <= M ; i ++) cin >> t[i] >> w[i];  //采药的时间,草药的数目。

    for(int i = 1 ; i <= T ; i ++)
        for(int j = 1 ; j <= M ; j ++)
        {
            f[i][j] = f[i][j - 1];
            if(t[j] <= i) //如果时间允许
            {
                f[i][j] = max(f[i][j - 1], f[i - t[j]][j - 1] + w[j]);
            }
        }
    cout << f[T][M] << endl;  //从前T的时间内采M株药草可以得到的最大价值

    return 0;
}


一维(AC)：
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N];

int main()
{
    int n, m;
    cin >> m >> n;

    for (int i = 1 ; i <= n ; i ++)
    {
        int w, v;
        cin >> w >> v;
        for (int j = m ; j >= w ; j --) f[j] = max(f[j], f[j - w] + v);
    }

    cout << f[m] << endl;

    return 0;
}