动态规划 C++ 求解

某学科老师布置了n个题目，每个题目都有相应的分数及截止日期。各个题目的分数及截止日期可能并不相同。对某题目而言，如果在该题目的截止日期前完成则可获得对应的分数，否则无法得分。假设每个题目均需要花费一天的时间来完成，这期间无法完成其他题目。请你设计算法指定题目的完成计划，从而使总的得分最大。

下面给出一个包含了7个题目及相应的分数、截止日期的实例：

题目

1

2

3

4

5

6

7

分数

6

7

2

1

4

5

1

截止日期（天）

1

1

3

3

2

2

4

对该实例而言，得分最大的作业完成方案为花费4天时间依次完成题目2,6,3,7。得分为15。

【输入形式】 

输入数据第一行为一个整数n (0 <= n <= 10000), 表示题目数目
之后n行各有两个整数, 第i行为 pi, di (1 <= pi, di <= 10000)，分别表示第i个题目的分数和截止时间

【输出形式】

一个整数, 为当前条件下的最大得分

【样例输入】

4 
50 2 
10 1 
20 2 
30 1

【样例输出】

80

贪心算法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<pair<int, int>> problems(n);
    for (int i = 0; i < n; ++i) {
        int p, d;
        cin >> p >> d;
        problems[i] = {p, d};
    }
    sort(problems.begin(), problems.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });

    int days_left = 0, max_d = 0;
    for (int i = 0; i < n; ++i) {
        int p = problems[i].first, d = problems[i].second;
        if (d > days_left) {
            max_d += p;
            ++days_left;
        }
    }

    cout << max_d << endl;

    return 0;
}

动态规划算法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<pair<int, int>> problems(n);
    int T = 0;
    for (int i = 0; i < n; ++i) {
        int p, d;
        cin >> p >> d;
        problems[i] = {p, d};
        T += d;
    }
    sort(problems.begin(), problems.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });

    vector<int> dp(T+1, 0);
    for (int i = 0; i < n; ++i) {
        int p = problems[i].first, d = problems[i].second;
        for (int j = T; j >= d; --j) {
            dp[j] = max(dp[j], dp[j-d] + p);
        }
    }

    cout << dp[T] << endl;

    return 0;
}