# 当前找到的最优方案：收益、内存、算力
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}

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

完整代码实现

"""
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

输入：

四个任务分别为：

任务	内存	算力	收益
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

输入：

组合	总内存	总算力	总收益	是否可行
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 中可以接受。

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

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

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

扩展思考

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

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

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

题目描述

输入格式

输出格式

示例

示例 1

示例 2

解题思路

第一步：理解问题本质

第二步：暴力解法

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

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

完整代码实现

示例推演

样例 1

样例 2

复杂度分析

易错点总结

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

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

3. `profit_unit` 要足够大

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

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

6. 空集是合法方案

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

扩展思考

相关题目