NASA的食物计划

题意

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

体积
质量
卡路里

要求在总体积不超过 H、总质量不超过 T 的前提下，最大化总卡路里。每种食品最多选一次。

思路

一句话本质：把体积和质量看成两维容量，每件食品最多选一次——二维费用 01 背包，把 dp 从一维数组扩充成二维即可。

先看最直接的暴力：

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$ ，显然不适合正式数据。

这题和普通 01 背包的区别在哪？

普通 01 背包只有一维容量（比如重量）；这题同时受体积 H 和质量 T 两维限制。每件食品消耗的资源也从一项变成两项。但本质仍然是"每个物品选或不选、容量限制下最优"——多了一维容量只是数组维度多了而已。

一维 dp[j] 怎么扩展到二维？

一维 dp[j] 表示容量 j 下的最大价值。二维 dp[j][k] 表示体积不超过 j、质量不超过 k 时的最大卡路里。转移同样做"选/不选"决策：

不选：dp[j][k] 保持不变
选：dp[j][k] = max(dp[j][k], dp[j - h_i][k - t_i] + k_i)

两个容量维度的枚举顺序有变化吗？

没有。因为每件食品最多选一次，两维容量都要倒序枚举。倒序保证当前食品不会在同一轮转移中被重复使用。

于是设：

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

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

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

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

状态表

这张表说明状态含义：

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

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:13
 * update_at: 2026-08-08 23:13
 * dp[j][k] 二维01背包
 */
#include <bits/stdc++.h>
using namespace std;

const int maxv = 405;
int H, T, n;
int dp[maxv][maxv];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> H >> T >> n;
    for (int i = 1; i <= n; ++i) {
        int h, t, k;
        cin >> h >> t >> k;
        for (int j = H; j >= h; --j)
            for (int l = T; l >= t; --l)
                dp[j][l] = max(dp[j][l], dp[j - h][l - t] + k);
    }
    cout << dp[H][T] << "\n";
    return 0;
}

复杂度

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

总结

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

容量从一维变成了二维

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

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析