算法-背包问题

算法思路

尽可能多的获得报酬，很容易想到背包问题，这里 d 是截止时间，那么我们可以用 m 来记录最大的截止时间，然后我们可以把所有物品按照 d 排序，从小到大枚举所有物品就 OK 了

#include<bits/stdc++.h>
using namespace std;
const int N = 5050; // 定义最大工作数量int t[N], d[N], p[N]; // 存储每项工作的耗时、截止时间和报酬
int n, m; // n 是工作数量，m 是最大截止时间
int f[N]; // 动态规划数组，f[j] 表示在时间 j 时可以获得的最大报酬struct node {int t, d, p; // 工作的结构体，包含耗时、截止时间和报酬
};
node a[N]; // 存储工作的结构体数组// 比较函数，按照截止时间从小到大排序
bool cmp(node a, node b) {return a.d < b.d;
}int main() {int k;cin >> k; // 读取测试数据的组数while (k--) {m = 0;cin >> n; // 读取工作数量for (int i = 1; i <= n; i++) {cin >> a[i].t >> a[i].d >> a[i].p; // 读取每项工作的耗时、截止时间和报酬m = max(m, a[i].d); // 更新最大截止时间}sort(a + 1, a + 1 + n, cmp); // 按照截止时间排序for (int i = 0; i <= m; i++)f[i] = 0; // 初始化动态规划数组for (int i = 1; i <= n; i++) {// 倒序遍历时间，确保每个工作只被处理一次for (int j = a[i].d; j >= a[i].t; j--) {// 更新动态规划数组f[j] = max(f[j], f[j - a[i].t] + a[i].p);}}int ans = 0;for (int i = 0; i <= m; i++)ans = max(ans, f[i]); // 找到最大报酬cout << ans << endl; // 输出结果}return 0;
}