榨取kkksc03

题意

有 n 个愿望。

第 i 个愿望需要：

m_i 的金钱
t_i 的时间

kkksc03 一共只有 M 元和 T 分钟。每个愿望最多完成一次，要求在总金钱和总时间都不超限的前提下，最多完成多少个愿望。

思路

先看最直接的暴力：

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// brute.cpp：小数据暴力解，使用 01 序列枚举每个愿望做或不做。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;                       // 愿望数量
int limit_money, limit_time; // 可用资源上限
int cost_money[MAXN];        // 每个愿望需要的金钱
int cost_time[MAXN];         // 每个愿望需要的时间
int choose_wish[MAXN];       // choose_wish[i] = 0/1，表示第 i 个愿望不做/做
int best_answer;             // 当前找到的最优答案

bool check() {
    int used_money = 0;
    int used_time = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_wish[i] == 1) {
            used_money += cost_money[i];
            used_time += cost_time[i];
        }
    }
    return used_money <= limit_money && used_time <= limit_time;
}

int calc_answer() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_wish[i] == 1) cnt++;
    }
    return cnt;
}

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_wish[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    cin >> n >> limit_money >> limit_time;
    for (int i = 1; i <= n; i++) {
        cin >> cost_money[i] >> cost_time[i];
    }

    best_answer = 0;
    dfs_choose(1);

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

brute.cpp 把每个愿望看成一个 01 选择：choose_wish[i] = 0/1 表示不做或做。递归先生成完整选择，叶子节点再检查总金钱和总时间是否超限，并统计能完成的愿望数量。

这个做法容易理解，但复杂度是 $O(2^n)$ ，只能用于小数据验证。

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

不过这题有两种资源限制：

金钱
时间

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

设：

dp[j][k] 表示在金钱不超过 j、时间不超过 k 的前提下，最多能完成多少个愿望

加入一个愿望 (m_i, t_i) 时：

不选它：状态不变
选它：从 dp[j - m_i][k - t_i] 转移，再加 1

所以有转移：

dp[j][k] = max(dp[j][k], dp[j - m_i][k - t_i] + 1)

由于每个愿望只能选一次，所以金钱和时间两维都必须倒序枚举。

状态表

这张表说明状态的含义：

状态	含义
`dp[j][k]`	金钱不超过 `j`、时间不超过 `k` 时，最多能完成多少个愿望

从这个状态定义可以看出，这题记录的是“资源上限下的最优值”，而不是具体选了哪几个愿望。也正因为如此，二维表已经足够表达最优解。

最后直接输出 dp[M][T] 即可。

DP 公式

设 $dp_{j,k}$ 表示金钱不超过 $j$ 、时间不超过 $k$ 时，最多能完成多少个愿望。处理第 $i$ 个愿望时：

dp_{j,k}=\max(dp_{j,k},\ dp_{j-m_i,k-t_i}+1)

其中 $j\geqslant m_i$ 且 $k\geqslant t_i$ 。两个容量都倒序枚举，最终答案为：

dp_{M,T}

公式解释：每个愿望最多做一次，同时消耗金钱和时间两个资源。选当前愿望时，必须从两个资源都扣掉后的状态转移过来，并让完成数量加一。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXM = 205;
const int MAXT = 205;

int n;                      // 愿望数量
int limit_money, limit_time; // 可用的金钱和时间上限
int cost_money[MAXN];       // 第 i 个愿望需要的金钱
int cost_time[MAXN];        // 第 i 个愿望需要的时间
int dp[MAXM][MAXT];         // dp[j][k] = 金钱不超过 j、时间不超过 k 时最多能满足多少个愿望

void read_input() {
    cin >> n >> limit_money >> limit_time;
    for (int i = 1; i <= n; i++) {
        cin >> cost_money[i] >> cost_time[i];
    }
}

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

    for (int i = 1; i <= n; i++) {
        // 两维容量都倒序，保证每个愿望最多只被选择一次。
        for (int j = limit_money; j >= cost_money[i]; j--) {
            for (int k = limit_time; k >= cost_time[i]; k--) {
                dp[j][k] = max(dp[j][k], dp[j - cost_money[i]][k - cost_time[i]] + 1);
            }
        }
    }

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

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(nMT)$
空间复杂度： $O(MT)$

总结

看到下面这种结构时，可以直接往二维费用背包上靠：

每个物品只能选一次
同时受两种资源限制
目标是最大化总收益

这题里“收益”就是完成愿望的个数，所以每个愿望的价值都看成 1，问题就变成一个标准模板。

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析