一道DP（动态规划）、01背包的模板题（么？）。

洛谷链接P1048

DP是什么？

DP是一种“用空间换时间”的算法，它将已经算好的答案存下来（子问题），再从父问题获取子问题的答案。

此题解释

给出采每种药花费的时间和价值，问在给定的时间内最多采药多少钱？

怎么写？

对于每种药，遍历那个f，假如装不进去或者装进去费空间的要死那就抄上一个；假如可以的话那就装进去！

代码！

#include<iostream>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, n;
    cin >> t >> n;
    int v[n + 1]; //价值
    int w[n + 1]; //时间
    int f[101][1001];

    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i++)
        for (int j = t; j >= 0; j--) {
            if (j < w[i])
                f[i][j] = f[i - 1][j]; //抄上一个（装不进去）
            else if ( f[i - 1][j] > f[i - 1][j - w[i]] + v[i] )
                f[i][j] = f[i - 1][j]; //抄上一个（装进去费空间）
            else
                f[i][j] = f[i - 1][j - w[i]] + v[i]; //装进去！
        }

    cout << f[n][t];
    return 0;
}