PP4900 最多分数（入门）

解题思路

第一步，识别问题类型。 每一种题目都可以无限次选择，选多少道都不受限制，这和"每种物品可以拿任意多个"的完全背包一模一样。我们把它套用完全背包的做法即可。

第二步，设计状态。 用 dp[j] 表示"花费正好为 j 时间时，能得到的最大分数"。一开始什么都没做，所以 dp[0]=0，其他都是 0。

第三步，写出转移。 对于第 i 种题目，它要花 t[i] 时间、得 p[i] 分。因为可以重复选，所以我们从小到大（正序）扫描时间 j：dp[j]=max(dp[j], dp[j-t[i]]+p[i])。正序循环能让同一种题目被多次使用，这正是完全背包的关键。

第四步，看例子。 样例中时间 300、有 4 种题目。选两次"120 时间 250 分"（共 240 时间 500 分），再选三次"20 时间 35 分"（共 60 时间 105 分），合计 300 时间、605 分，正好得到答案 605。

边界情况。 如果某种题目的时间超过了总时间 m，那么它的循环不会执行，直接跳过即可。注意总分数可能很大，要开 long long。

参考代码

// P4900 最多分数 完全背包：每种题目可以重复选
#include <iostream>
using namespace std;
long long dp[10005]; // dp[j] 用 j 时间能得到的最大分数
int p[10005], t[10005]; // p 分数, t 时间
int main() {
    int m, n, i, j;
    cin >> m >> n;
    for (i = 0; i < n; i++) cin >> p[i] >> t[i];
    // 完全背包：正序循环，同一种题目能重复取
    for (i = 0; i < n; i++)
        for (j = t[i]; j <= m; j++)
            if (dp[j - t[i]] + p[i] > dp[j]) dp[j] = dp[j - t[i]] + p[i];
    cout << dp[m] << endl;
    return 0;
}

复杂度分析

时间复杂度是 O(n×m)（n 为题目种类数，m 为竞赛时间），本题 m,n 都不超过 1 万，完全可行。空间复杂度是 O(m)，只用了一个一维数组。