L 国的战斗之间谍

题意

有 N 个候选间谍。

第 i 个人有三项属性：

A：能得到多少资料
B：伪装能力有多差，也就是会增加多少探查风险
C：需要多少工资

敌人的探查能力上限是 M，手里的钱数上限是 X。要求在总风险和总工资都不超限的前提下，让拿到的资料总量最大。

思路

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66// brute.cpp：小数据暴力解，使用 01 序列枚举每个间谍派或不派。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
int limit_detect;          // 总探查风险上限
int limit_money;           // 总工资上限
int info_value[MAXN];      // 资料量
int detect_cost[MAXN];     // 探查风险
int money_cost[MAXN];      // 工资
int choose_spy[MAXN];      // choose_spy[i] = 0/1，表示第 i 个间谍不派/派
int best_answer;           // 当前找到的最大资料量

bool check() {
    int used_detect = 0;
    int used_money = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_spy[i] == 1) {
            used_detect += detect_cost[i];
            used_money += money_cost[i];
        }
    }
    return used_detect <= limit_detect && used_money <= limit_money;
}

int calc_answer() {
    int total_info = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_spy[i] == 1) total_info += info_value[i];
    }
    return total_info;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_answer();
            if (best_answer < value) best_answer = value;
        }
        return;
    }

    // 第 dep 个间谍的 01 选择：0 不派，1 派。
    for (int i = 0; i <= 1; i++) {
        choose_spy[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> limit_detect >> limit_money;
    for (int i = 1; i <= n; i++) {
        cin >> info_value[i] >> detect_cost[i] >> money_cost[i];
    }

    best_answer = 0;
    dfs_choose(1);

    cout << best_answer << '\n';
    return 0;
}

brute.cpp 把每个人看成一个 01 选择：choose_spy[i] = 0/1 表示不派或派。递归先生成完整选择，叶子节点再检查总风险和总工资是否超限，并统计最大资料量。

这个做法正确但复杂度是 $O(2^N)$ ，只能做小数据验证。

关键观察是：每个人都只有“选 / 不选”两种状态，并且每个人最多只能选一次，所以本质上是 0/1 背包。

不过这题同时有两种限制：

总探查风险不能超过 M
总工资不能超过 X

因此它不是普通一维背包，而是二维费用 0/1 背包。

设：

dp[j][k] 表示总风险不超过 j、总工资不超过 k 时，最多能拿到多少资料

加入一个人 (A_i, B_i, C_i) 时：

不选他：状态不变
选他：从 dp[j - B_i][k - C_i] 转移，再加上 A_i

所以有转移：

dp[j][k] = max(dp[j][k], dp[j - B_i][k - C_i] + A_i)

由于每个人只能选一次，两维容量都必须倒序枚举。

状态表

这张表说明状态的含义：

状态	含义
`dp[j][k]`	总风险不超过 `j`、总工资不超过 `k` 时，最多能拿到多少资料

这个定义说明，我们只关心在给定资源限制下的最优资料量，不需要记录具体选了哪些人。因此用一张二维表就能完整表达状态。

最后输出 dp[M][X] 即可。

DP 公式

设 $dp_{j,k}$ 表示总风险不超过 $j$ 、总工资不超过 $k$ 时，最多能拿到多少资料。处理第 $i$ 个人时：

dp_{j,k}=\max(dp_{j,k},\ dp_{j-B_i,k-C_i}+A_i)

其中 $j\geqslant B_i$ 且 $k\geqslant C_i$ 。由于每个人只能选一次，两维容量都倒序枚举。最终答案为：

dp_{M,X}

公式解释：每个间谍只能招募一次，所以是二维 0/1 背包。风险和工资是两个容量，资料量是收益；只有两个容量都足够时，才能考虑选这个人。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXM = 1005;
const int MAXX = 1005;

int n;
int limit_detect;          // 敌人的探查能力上限
int limit_money;           // 手头的钱数上限
int info_value[MAXN];      // 第 i 个间谍能拿到的资料量
int detect_cost[MAXN];     // 第 i 个间谍带来的探查风险
int money_cost[MAXN];      // 第 i 个间谍需要的工资
int dp[MAXM][MAXX];        // dp[j][k] = 风险不超过 j、金钱不超过 k 时最多能拿到多少资料

void read_input() {
    cin >> n >> limit_detect >> limit_money;
    for (int i = 1; i <= n; i++) {
        cin >> info_value[i] >> detect_cost[i] >> money_cost[i];
    }
}

void solve() {
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        // 两维容量都倒序，保证每个间谍最多只选一次。
        for (int j = limit_detect; j >= detect_cost[i]; j--) {
            for (int k = limit_money; k >= money_cost[i]; k--) {
                dp[j][k] = max(dp[j][k],
                               dp[j - detect_cost[i]][k - money_cost[i]] + info_value[i]);
            }
        }
    }

    cout << dp[limit_detect][limit_money] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(NMX)$
空间复杂度： $O(MX)$

总结

看到下面这种结构时，就应该往二维费用背包上想：

每个对象最多选一次
同时消耗两种资源
目标是最大化总价值

这题里“价值”就是资料量，因此直接套二维费用 0/1 背包模板即可。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。