算法
(01背包) $O(n * 2000)$
典型的 $01$ 背包问题。
这里的花费不是体积,而是时间。
用 f[i]
表示第 $i$ 时刻最大能救多少价值。
转移方程:
$$
f[i] = \max(f[i], f[i - t[j]] + p[j]) \ (i - t[j] + p[j]) \leqslant d[j])
$$
因此先对物品按 $d[i]$ 从小到大排序,然后依次更新。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
bool chmax(int& a, int b) { if (a < b) { a = b; return 1; } return 0; }
const int N = 110;
const int M = 2010;
struct node {
int d, t, p, id;
bool operator < (const node& b) const {
return d < b.d;
}
} a[N];
int f[M];
vector<int> g[M];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].t >> a[i].d >> a[i].p;
a[i].id = i;
}
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
for (int j = a[i].d - 1; j >= a[i].t; --j) {
if (f[j] < f[j - a[i].t] + a[i].p) {
f[j] = f[j - a[i].t] + a[i].p;
g[j].clear();
g[j] = g[j - a[i].t];
g[j].push_back(a[i].id);
}
}
}
int ans = 0, t = 0;
for (int i = 1; i <= 2000; ++i) {
if (f[i] > ans) {
ans = f[i];
t = i;
}
}
cout << ans << '\n';
cout << g[t].size() << '\n';
for (auto& x : g[t]) cout << x << " ";
return 0;
}