L国的战斗之间谍（洛谷）

题目背景 L国即将与I国发动战争！！

题目描述 俗话说的好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。

你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。

已知敌人的探查间谍能力为 M（即去的所有人B的和要小于等于M）和手头有 X 元钱，请问能拿到多少资料？

输入格式 N M X A₁ B₁ C₁ A₂ B₂ C₂ ……………… A_N B_N C_N

输出格式 能得到的资料总数

输入样例 3 10 12 10 1 11 1 9 1 7 10 12

输出样例 11

数据范围 1 ≤ n ≤ 100, 1 ≤ m ≤ 1000, 1 ≤ x ≤ 1000

---

题解 二维费用的01背包（空间优化）：

#include <iostream> using namespace std; const int N = 1010; int n, V1, V2; int v1[N], v2[N], w[N], f[N][N]; int main() { cin >> n >> V1 >> V2; for (int i = 1; i <= n; i ++) cin >> w[i] >> v1[i] >> v2[i]; for (int i = 1; i <= n; i ++) for (int j = V1; j >= v1[i]; j --) for (int k = V2; k >= v2[i]; k --) f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + w[i]); cout << f[V1][V2] << endl; return 0; }