P5311. 双资源约束下的运维任务收益最大化

场次：2026年8月26日 · 来源：CodeFun2000 P5311

题目描述

运维团队在批量处理服务器运维任务时，需要合理分配有限的内存资源和算力资源。每个任务执行后会占用一定量的资源，同时能够带来对应的运维收益，例如增强系统稳定性、降低变更风险等。

现有$n$个待执行任务，系统最多可以提供$A$单位内存和$B$单位算力。对于第$i$个任务，执行它需要消耗$x_i$单位内存、$y_i$单位算力，并可以获得收益$w_i$。

请从所有任务中选择若干个执行，使所选任务的内存消耗总量不超过$A$，算力消耗总量不超过$B$，并使获得的总运维收益最大。

在得到最大收益的情况下，还需要确定对应方案的内存总消耗和算力总消耗。若存在多个方案获得的收益相同，则优先选择内存消耗更小的方案；若内存消耗也相同，则选择算力消耗更小的方案。

输入格式

第一行输入三个整数$n$、$A$、$B$（$1 \le n \le 100$，$1 \le A \le 500$，$1 \le B \le 500$），分别表示任务数量、可使用的最大内存和可使用的最大算力。

第二行到$(n+1)$行，每行输入三个正整数$x_i$、$y_i$、$w_i$（$1 \le x_i \le 100$，$1 \le y_i \le 100$，$1 \le w_i \le 100$），分别表示第$i$个任务的内存消耗、算力消耗和运维收益。

输出格式

输出三个整数，用空格分隔：

1. 最大运维收益
2. 达到最大收益时的总内存消耗
3. 达到最大收益时的总算力消耗

若有多组方案都能达到最大收益，输出内存消耗最小的方案；若内存消耗也相同，则输出算力消耗最小的方案。

示例

示例 1

输入：

4 12 10
5 4 8
6 3 10
4 6 9
3 2 5

输出：

19 10 9

示例 2

输入：

3 9 8
4 3 7
5 4 9
3 4 6

输出：

16 9 7

说明：

选择第1、2个任务，总内存$(4+5=9)$，总算力$(3+4=7)$，总收益$(7+9=16)$

---

解题思路

第一步：理解问题本质

每个任务都是一件“物品”，它同时消耗两种资源：

• 内存 $x_i$
• 算力 $y_i$

并获得收益 $w_i$。每个任务只能选择一次，要求两种资源的总消耗分别不超过 $A$ 和 $B$，这就是一个二维 0/1 背包问题。

与普通背包不同的是，题目还规定了次级目标：

1. 先最大化总收益；
2. 收益相同时，最小化总内存；
3. 内存也相同时，最小化总算力。

因此 DP 状态不能只记录“最大收益”，还要能比较同收益方案的资源消耗。

第二步：暴力解法

最直接的做法是枚举所有任务子集。对于每个子集，统计总内存、总算力和总收益，保留满足容量限制且字典序最优的方案。

# 当前找到的最优方案：收益、内存、算力
best_profit = 0
best_memory = 0
best_compute = 0

# mask 的二进制表示就是每个任务“选/不选”的状态：
# 第 i 位为 1 表示选择第 i 个任务，为 0 表示不选。
# n 个任务一共有 2^n 种选法，所以 mask 从 0 枚举到 2^n - 1。
for mask in range(1 << n):
    memory = 0
    compute = 0
    profit = 0

    # 逐位检查当前 mask 选了哪些任务
    for i in range(n):
        # (mask >> i) & 1 取出 mask 的第 i 位
        if (mask >> i) & 1:
            memory += x[i]
            compute += y[i]
            profit += w[i]

    # 两种资源都不能超过上限，否则这个方案非法
    if memory > A or compute > B:
        continue

    # 按题目要求比较三个目标：
    # 1. 收益更大，直接更新；
    # 2. 收益相同，但内存更小，更新；
    # 3. 收益、内存都相同，但算力更小，更新。
    if (profit > best_profit
            or (profit == best_profit and memory < best_memory)
            or (profit == best_profit and memory == best_memory
                and compute < best_compute)):
        best_profit = profit
        best_memory = memory
        best_compute = compute

这段代码故意把三个比较条件完整写出来，方便对照题意。理解之后，也可以把三个目标放进元组，利用 Python 元组“从左到右逐项比较”的规则来简化：

# (收益, -内存, -算力)
best = (0, 0, 0)

for mask in range(1 << n):
    memory = compute = profit = 0
    for i in range(n):
        if (mask >> i) & 1:
            memory += x[i]
            compute += y[i]
            profit += w[i]

    if memory <= A and compute <= B:
        # 收益越大，元组越大；
        # 收益相同时，-内存越大（内存越小），元组越大；
        # 内存也相同时，-算力越大（算力越小），元组越大。
        best = max(best, (profit, -memory, -compute))

例如：

• (19, -10, -9) 和 (18, -11, -7) 比较：第一项 19 > 18，前者赢；
• (19, -10, -9) 和 (19, -9, -12) 比较：第一项相同，第二项 -10 < -9，后者（内存 9）赢；
• (19, -10, -9) 和 (19, -10, -8) 比较：前两项相同，第三项 -9 < -8，后者（算力 8）赢。

子集数量是 $2^n$。当 $n=100$ 时，$2^{100}$ 远远超出任何评测机的时间限制，必须利用容量上限做动态规划。

第三步：优化解法——二维 DP + 三元组

定义：

$$dp[a][b] = \text{在内存上限为 } a \text{、算力上限为 } b \text{ 时，能得到的最优方案}$$

其中“最优”按三元组比较：

$$(\text{收益},\ -\text{已用内存},\ -\text{已用算力})$$

这里有两层信息：a,b 是容量上限，决定方案装不装得下；元组里的 -已用内存,-已用算力 是这个方案实际消耗的资源，用于在收益相同时打破平局。把实际消耗取负，是为了让 Python 的元组比较直接实现“收益越大越好；收益相同时内存越小越好；内存也相同时算力越小越好”。例如 (19,-10,-9) 和 (19,-9,-12) 收益相同，但后者的第二个分量 -9 更大，所以后者（内存 9）更优。

初始时所有 $dp[a][b] = (0, 0, 0)$，表示不选任何任务。对每个任务 $(x_i, y_i, w_i)$，倒序枚举两种容量：

$$dp[a][b] = \max\left(dp[a][b],\ dp[a-x_i][b-y_i] + (w_i, -x_i, -y_i)\right)$$

注意：公式里的 + 是数学上的逐分量相加。在 Python 里不能直接写 tuple + tuple，那会把两个元组拼接起来；应该写成 (p + w, -m - x, -c - y)。本题最终采用整数编码，不需要真的构造元组。

倒序枚举的原因和普通 0/1 背包一样：如果正序枚举，$dp[a-x_i][b-y_i]$ 可能已经包含了当前任务，导致同一个任务被重复选择。

这个做法的时间复杂度是 $O(nAB)$，已经可以接受。但每个状态都要保存和比较一个三元组，在 Python 中会产生大量元组对象，常数较大。

第四步：最优解法——把三元组编码成一个整数

我们希望仍然只比较一个整数，同时保留“收益优先、内存其次、算力最后”的顺序。

令：

$$\text{memory\_unit} = B + 1$$ $$\text{profit\_unit} = A \times \text{memory\_unit} + B + 1$$

对任意方案，定义编码分数：

$$\text{score} = \text{收益} \times \text{profit\_unit} - \text{内存} \times \text{memory\_unit} - \text{算力}$$

为什么这个编码能表达三级排序？

• 设两个方案的收益分别为 $p_1 > p_2$。即使收益高的方案资源消耗最大、收益低的方案资源消耗为 $0$，两者分数之差也至少是

  $$(p_1-p_2)\times \text{profit\_unit} - \text{最大惩罚} \ge \text{profit\_unit} - (A\times\text{memory\_unit}+B) = 1 > 0$$

  所以收益高的方案一定赢。

• 当收益相同时，分数只由 $-\text{内存}\times\text{memory\_unit}-\text{算力}$ 决定。因为 $\text{memory\_unit}=B+1$ 严格大于任何可能的算力消耗（算力不超过 $B$），内存每增加 $1$，惩罚增加 $B+1$；而算力最多只能减少 $B$，所以净惩罚仍然至少增加 $1$，不可能被算力的减少抵消。于是内存小的方案一定赢。

• 内存也相同时，分数只由 $-\text{算力}$ 决定，算力小的方案赢。

这样就把三级比较压缩成了一个整数比较。DP 转移变成：

$$dp[a][b] = \max\left(dp[a][b],\ dp[a-x_i][b-y_i] + w_i\times\text{profit\_unit} - x_i\times\text{memory\_unit} - y_i\right)$$

最后从 $dp[A][B]$ 反解：

$$\text{收益} = \left\lceil \frac{\text{score}}{\text{profit\_unit}} \right\rceil$$ $$\text{惩罚} = \text{收益}\times\text{profit\_unit} - \text{score}$$ $$\text{内存} = \left\lfloor \frac{\text{惩罚}}{\text{memory\_unit}} \right\rfloor,\qquad \text{算力} = \text{惩罚} \bmod \text{memory\_unit}$$

实现时把二维表压成一维数组，并用倒序循环避免任务重复使用。

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码1342 帧 · 录制输入

"""
P5311. 双资源约束下的运维任务收益最大化 - 二维 0/1 背包

输入格式：
- 第 1 行：三个整数 n、A、B；
- 接下来 n 行：每行三个正整数 x_i、y_i、w_i。

输出格式：
- 一行三个整数：最大收益、总内存消耗、总算力消耗。

时间复杂度：O(n * A * B)
空间复杂度：O(A * B)
"""

import sys


def solve():
    # 一次性读入全部整数。ACM 模式下用 buffer.read() 比逐行 input() 更快，
    # 也不会因为行末空格或空行影响解析。
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    max_memory = int(next(it))
    max_compute = int(next(it))

    # dp 本来是二维表：dp[a][b] 表示“内存上限为 a、算力上限为 b”时的最优分数。
    # 为了减少 Python 嵌套列表的寻址开销，这里把它压成一维数组：
    #   二维下标 (a, b)  ->  一维下标 a * width + b
    # 其中 width 是一行里有多少个算力状态（b 从 0 到 max_compute）。
    width = max_compute + 1
    dp = [0] * ((max_memory + 1) * width)

    # 下面两个“单位”用来把三个目标编码成一个整数：
    #
    #   score = 收益 * profit_unit - 内存 * memory_unit - 算力
    #
    # memory_unit 必须严格大于算力上限，这样“内存多 1”造成的扣分
    # 一定大于“算力减少最多 B”带来的补偿，保证同收益时内存优先。
    #
    # profit_unit 必须严格大于所有方案可能产生的最大惩罚值
    # memory * memory_unit + compute（最多 A * memory_unit + B），
    # 这样“收益多 1”一定大于任何资源扣分差，保证收益优先。
    memory_unit = max_compute + 1
    profit_unit = max_memory * memory_unit + max_compute + 1

    for _ in range(n):
        # 读入当前任务：内存消耗、算力消耗、收益。
        memory = int(next(it))
        compute = int(next(it))
        profit = int(next(it))

        # 如果单个任务的内存或算力已经超过上限，它不可能出现在任何合法方案里。
        if memory > max_memory or compute > max_compute:
            continue

        # 选择当前任务，相当于在分数上加上：
        #   收益 * profit_unit        （收益越多越好）
        #   - 内存 * memory_unit      （内存越少越好）
        #   - 算力                    （算力越少越好）
        gain = profit * profit_unit - memory * memory_unit - compute

        # 0/1 背包的容量必须倒序枚举。
        # 以内存 a 为例：如果从小到大枚举，dp[a - memory] 可能已经在本轮
        # 选过当前任务，再转移就会把同一个任务选两次。
        for a in range(max_memory, memory - 1, -1):
            # 一维数组中，容量 a 这一行的起点
            base = a * width
            # 选当前任务之前，内存上限是 a - memory，对应上一行的起点
            prev_base = (a - memory) * width

            # 算力 b 同样要倒序枚举，原因和上面的内存完全一样。
            for b in range(max_compute, compute - 1, -1):
                # 不选当前任务时，dp[base + b] 保持原值；
                # 选当前任务时，从“扣掉当前任务消耗”的旧状态转移过来。
                candidate = dp[prev_base + b - compute] + gain
                index = base + b
                if candidate > dp[index]:
                    dp[index] = candidate

    # 容量上限为 (max_memory, max_compute) 的状态，在扁平数组的最后一个位置。
    best = dp[max_memory * width + max_compute]

    # score = profit * profit_unit - penalty，其中 0 <= penalty < profit_unit。
    # 因为 score 可能被 penalty 拉低，直接整除会少算 1，所以这里用向上取整。
    profit = (best + profit_unit - 1) // profit_unit
    penalty = profit * profit_unit - best

    # penalty = 内存 * memory_unit + 算力。
    # 因为算力 < memory_unit，所以整除得到内存，取余得到算力。
    memory_used = penalty // memory_unit
    compute_used = penalty % memory_unit

    print(profit, memory_used, compute_used)


if __name__ == "__main__":
    solve()

---

示例推演

样例 1

输入：

4 12 10
5 4 8
6 3 10
4 6 9
3 2 5

四个任务分别为：

任务	内存	算力	收益
1	5	4	8
2	6	3	10
3	4	6	9
4	3	2	5

枚举接近最优的几种组合：

组合	总内存	总算力	总收益	是否可行
1 + 2	11	7	18	是
1 + 3	9	10	17	是
1 + 4	8	6	13	是
2 + 3	10	9	19	是
2 + 4	9	5	15	是
3 + 4	7	8	14	是
1 + 2 + 4	14	—	—	内存超限
1 + 3 + 4	12	12	22	算力超限

最大收益是 $19$，对应任务 2 和任务 3，总内存 $6+4=10$，总算力 $3+6=9$，所以输出：

19 10 9

用编码验证：$\text{memory\_unit}=11$，$\text{profit\_unit}=12\times11+10+1=143$。

• 方案 2+3：$19\times143-10\times11-9=2598$
• 方案 1+2：$18\times143-11\times11-7=2446$

$2598>2446$，因此收益 19 的方案胜出。反解时：

$$\text{收益}=\left\lceil\frac{2598}{143}\right\rceil=19$$ $$\text{惩罚}=19\times143-2598=119$$ $$\text{内存}=119\div11=10,\qquad \text{算力}=119\bmod11=9$$

样例 2

输入：

3 9 8
4 3 7
5 4 9
3 4 6

组合	总内存	总算力	总收益	是否可行
1 + 2	9	7	16	是
1 + 3	7	7	13	是
2 + 3	8	8	15	是
1 + 2 + 3	12	11	22	内存、算力都超限

最优方案是任务 1 和任务 2，总内存 $4+5=9$，总算力 $3+4=7$，输出：

16 9 7

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举子集	$O(2^n \cdot n)$	$O(n)$	$n=100$ 时不可行
二维 DP + 三元组	$O(nAB)$	$O(AB)$	正确，但 Python 元组比较常数较大
二维 DP + 整数编码	$O(nAB)$	$O(AB)$	本题采用，状态只比较一个整数

本题最大规模为 $n=100$、$A=B=500$，转移次数约为 $100\times500\times500=2.5\times10^7$，在 Python 中可以接受。

---

易错点总结

1. 只记录最大收益，忽略次级排序

如果 dp[a][b] 只存最大收益，那么当多个方案收益相同时，无法知道哪个方案的内存更小。必须把内存、算力一起纳入状态比较。

2. memory_unit 要严格大于算力上限

应取 memory_unit = B + 1，不能取 memory_unit = B。否则当算力恰好等于 $B$ 时，$(\text{内存}=1,\text{算力}=0)$ 与 $(\text{内存}=0,\text{算力}=B)$ 可能得到相同的惩罚值，导致内存和算力的优先级错乱。

3. profit_unit 要足够大

profit_unit 必须严格大于所有可能方案的最大惩罚值：

$$\text{profit\_unit} > A\times\text{memory\_unit}+B$$

代码中取 profit_unit = A * memory_unit + B + 1。如果 profit_unit 太小，收益差 $1$ 可能被资源消耗的差值抵消，导致程序选择收益更低但资源更少的方案。

4. 0/1 背包的两种容量都要倒序枚举

内存和算力都必须从大到小枚举。只要有一个维度正序，当前任务就可能在同一轮中被重复使用。

5. 超过容量的任务要跳过

如果某个任务的 $x_i>A$ 或 $y_i>B$，它不可能被任何合法方案选中。提前跳过可以减少无效转移。

6. 空集是合法方案

如果所有任务都超过容量，答案应为 0 0 0。DP 初始化为 $0$ 正好对应“不选任何任务”。

7. 反解收益时要用向上取整

因为 $\text{score}=\text{收益}\times\text{profit\_unit}-\text{惩罚}$，且惩罚可能大于 $0$，直接整除会少算 $1$。代码中使用：

profit = (best + profit_unit - 1) // profit_unit

---

扩展思考

• 二维背包的本质：每个物品同时占用两种容量，状态必须同时记录两种剩余容量。维度每增加一维，时间复杂度就多乘一个容量上限。
• 数据范围更大时：如果 $A$、$B$ 达到 $10^5$，$O(nAB)$ 不再可行。可以考虑按收益做 DP、Pareto 前沿剪枝，或者当 $n$ 较小时使用 meet-in-the-middle。
• 只求最大收益时：不需要编码，直接用普通的二维 0/1 背包即可，代码会更短。
• 多组测试数据：本题只有一组输入。如果题目改成多组，只需要在外层循环读取每组并重新初始化 DP 数组。

---

相关题目

• 动态规划