$\color{red}{DP}$——目录

题目大意：给你一些物品然后给你一些时间，每个物品想要拿到一定的时间，并会获得一定的价值，问最大价值。

我们会惊奇的发现，每个物品的时间都是每一个物品需要花费的，也就是01背包问题中的体积，同理得价值就是01背包问题里的价值。
既然这样我们就把它转化成了01背包问题。

$$ 闫氏DP分析法 $$

1. 状态表示——集合：$f[i][j]$ 表示考虑前 $i$ 个物品，且花费总时间不超过 $j$ 的集合下能获得的最大价值。
2. 状态表示——属性：因为是求最大价值，故为 $max$。
3. 状态计算——集合划分：考虑第 $i$ 个物品选不选。
   • 不选或选不了（剩余时间不够 $j < v[i]$）：$f[i - 1][j]$。
   • 选：$f[i - 1][j - v[i]] + w[i]$。首先你对第i个物品进行了你的抉择，所以前一维变成了 $i - 1$，接着因为使用了 $v[i]$ 的体积，所以应该是$j - v[i]$，最后你要把它带来的价值加上，所以要加上 $w[i]$。

至此我们就分析完毕

完整代码，时间复杂度：$O(nm)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N], w[N];
int f[N][N * 10];

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

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

当然相当于01背包，f数组也可以变成一维。

完整代码，时间复杂度：$O(nm)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

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

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