NASA的食物计划

题意

给出若干种食品，每种食品有：

体积
质量
卡路里

要求在总体积不超过 H、总质量不超过 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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，使用 01 序列枚举每个食品选或不选。

int H, T, n;
int h[55], t[55], k[55];
int choose_food[55]; // choose_food[i] = 0/1，表示第 i 个食品不选/选
int ans;

bool check() {
    int total_h = 0;
    int total_t = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_food[i] == 1) {
            total_h += h[i];
            total_t += t[i];
        }
    }
    return total_h <= H && total_t <= T;
}

int calc_answer() {
    int total_cal = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_food[i] == 1) total_cal += k[i];
    }
    return total_cal;
}

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

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

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

    cin >> H >> T;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> t[i] >> k[i];
    }

    ans = 0;
    dfs_choose(1);

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

brute.cpp 把每个食品看成一个 01 选择：choose_food[i] = 0/1 表示不选或选。递归先生成完整选择，叶子节点再检查总体积和总质量是否超限，并统计最大卡路里。

这个做法是最直观的，但复杂度是 $2^n$ ，显然不适合正式数据。

这题本质上就是 0/1 背包，只不过容量有两维：

第一维是体积
第二维是质量

于是设：

dp[j][l] 表示体积不超过 j、质量不超过 l 时能获得的最大卡路里

加入一个食品 (h_i, t_i, k_i) 时：

不选它：状态不变
选它：从 dp[j-h_i][l-t_i] 转移，再加上 k_i

因为每种食品只能选一次，所以两维容量都必须倒序枚举。

状态表

这张表说明状态含义：

状态	含义
`dp[j][l]`	体积不超过 `j`、质量不超过 `l` 时的最大卡路里

DP 公式

设 $dp_{j,l}$ 表示体积不超过 $j$ 、质量不超过 $l$ 时能获得的最大卡路里。处理食品 $i$ 时：

dp_{j,l}=\max(dp_{j,l},\ dp_{j-h_i,l-t_i}+k_i)

其中需要满足 $j\geqslant h_i$ 且 $l\geqslant t_i$ 。由于每种食品只能选一次，两个容量维度都要倒序枚举。最终答案为：

dp_{H,T}

公式解释：这是 0/1 背包的二维容量版本。选择当前食品时，体积和质量都要消耗对应额度，所以从 j-h_i,l-t_i 转移；倒序枚举保证一个食品不会被重复使用。

代码

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

const int MAXC = 405;

int H, T, n;
int h[55], t[55], k[55];
int dp[MAXC][MAXC]; // dp[j][l]：体积不超过 j、质量不超过 l 时的最大卡路里

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

    cin >> H >> T;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> t[i] >> k[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = H; j >= h[i]; j--) {
            for (int l = T; l >= t[i]; l--) {
                dp[j][l] = max(dp[j][l], dp[j - h[i]][l - t[i]] + k[i]);
            }
        }
    }

    cout << dp[H][T] << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nHT)$
空间复杂度： $O(HT)$

总结

这题和普通 0/1 背包的区别只有一点：

容量从一维变成了二维

所以只要把状态扩成 dp[体积][质量]，并继续保持倒序枚举容量，就能直接解决。

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析