双配置训练任务的最优资源调度

动态规划约 4276 字大约 14 分钟

P5346. 双配置训练任务的最优资源调度

场次：2026年9月4日 · 来源：CodeFun2000 P5346

题目描述

一个模型训练集群需要依次执行 $n$ 个任务。对于任意第 $i$ 个任务，调度系统已经给出两套候选配置，它们在计算资源占用和训练耗时上各有差异。

具体地，若第 $i$ 个任务采用配置 1，资源消耗为 $c_1$ ，训练耗时为 $t_1$ ；若采用配置 2，资源消耗为 $c_2$ ，训练耗时为 $t_2$ 。资源统一按照“CPU 核心数 + GPU 显存 GB”计量，集群可使用的总资源量为 $C$ 。

现在要为每个任务选定一套配置，且每个任务只能选择两套之一。所有任务资源消耗的总和不得超过 $C$ 。在这些合法选择中，目标是最小化所有任务的总训练耗时，并进一步确定最优方案实际消耗的资源量以及未被使用的剩余资源量。

如果多个合法方案具有相同的最小总训练耗时，则取其中实际资源消耗最少的一个作为最终方案。

约束条件：

任务数量 $n$ 在 1 到 100 之间。
总资源上限 $C$ 在 1 到 1000 之间。
每个任务的 $c_1$ 、 $t_1$ 、 $c_2$ 、 $t_2$ 均为 1 到 100 之间的正整数。

输入格式

第一行给出两个整数 $n$ 和 $C$ ，依次代表任务数量和总资源上限。

接下来的 $n$ 行中，第 $i$ 行包含四个正整数 $c_1$ 、 $t_1$ 、 $c_2$ 、 $t_2$ ，分别对应该任务配置 1 的资源消耗、配置 1 的训练耗时、配置 2 的资源消耗、配置 2 的训练耗时。

输出格式

输出共三个整数，用单个空格分隔，依次为：满足资源限制的最小总训练耗时；该最小耗时方案中实际使用的资源总量；以及 $C$ 减去该实际使用资源量后的剩余资源。

示例

示例 1

输入：

输出：

7 8 2

说明：

任务 1 选择配置 2，资源消耗为 $2$ ，耗时 $3$ ；任务 2 选择配置 2，资源消耗为 $5$ ，耗时 $2$ ；任务 3 选择配置 1，资源消耗为 $1$ ，耗时 $2$ 。

总资源消耗为 $2+5+1=8$ ，不超过 $C=10$ ；总耗时为 $3+2+2=7$ 。每个任务各自的最小耗时之和为 $3+2+2=7$ ，所以无法再降低总耗时。

任务 3 两种配置耗时相同，配置 1 的资源更少，因此选择配置 1。剩余资源为 $10-8=2$ 。

示例 2

输入：

1 1
1 5 2 3

输出：

5 1 0

说明：

总资源上限为 1。任务 1 的配置 1 资源消耗为 1，可以放入；配置 2 资源消耗为 2，超过上限，不可行。

因此唯一合法选择是配置 1，总耗时 5，实际消耗资源 1，剩余资源 $1-1=0$ 。

示例 3

输入：

2 5
3 4 2 6
2 5 4 1

输出：

9 5 0

说明：

所有不超过资源上限的选择中，总耗时最少的是：任务 1 选择配置 1，任务 2 选择配置 1。

该方案资源消耗为 $3+2=5$ ，总耗时为 $4+5=9$ ，刚好等于资源上限。

若任务 1 选择配置 2，任务 2 选择配置 1，则总耗时为 $6+5=11$ ，资源消耗为 $2+2=4$ ，虽然资源更少但耗时更大。

其他方案例如任务 2 选择配置 2 会超过资源上限。因此最优输出依次为 9、5、0。

示例 4

输入：

输出：

42 19 981

说明：

资源上限 1000 很充足，可以在每个任务上独立选择耗时更小的配置。

任务 1 选择配置 1，耗时 20，资源 10。任务 2 两种配置耗时都为 15，选择资源更少的配置 1，资源 3。任务 3 选择配置 1，耗时 7，资源 6。

总耗时为 $20+15+7=42$ ，总资源消耗为 $10+3+6=19$ ，剩余资源为 $1000-19=981$ 。

解题思路

第一步：理解问题本质

每个任务都必须且只能从两套配置里选一套，不能跳过，也不能两套都要。这相当于：有 $n$ 个“组”，每组里恰好两件物品，必须挑一件——这就是分组背包里最简单的一种（每组两件）。

同时题目有两级目标：

先让总训练耗时最小；
总耗时相同时，让实际消耗的资源最少。

这两个目标必须一起记住：如果只保留“最小耗时”这一个数字、不记录它对应的资源量，事后就无法知道是哪一个资源量达到的——而答案里恰好要输出这个资源量。

最后输出的是“最小耗时、该方案实际消耗的资源、剩余资源”，所以资源消耗不是中间量，而是答案的一部分，必须准确。

第二步：暴力解法

$n$ 个任务，每个任务两种选择，一共有 $2^n$ 种方案。逐个枚举，筛掉超预算的，再按两级目标取最优：

import itertools

best_time = best_cost = None
for choice in itertools.product((0, 1), repeat=n):
    time = cost = 0
    for i, pick in enumerate(choice):
        c, t = configs[i][pick]          # configs[i] = [(c1, t1), (c2, t2)]
        time += t
        cost += c
    if cost > C:
        continue                          # 超出资源上限，方案非法
    if best_time is None or (time, cost) < (best_time, best_cost):
        best_time, best_cost = time, cost

这个写法本身是对的：元组 (time, cost) 的比较恰好就是“先比耗时、再比资源”。但 $n$ 最大 $100$ ， $2^{100}$ 完全不可行。

第三步：优化解法——按资源做 DP（每个任务必须选一次）

把“已经用掉多少资源”作为状态。设

dp[r] = \text{处理完前 } i \text{ 个任务后，资源恰好用掉 } r \text{ 时的最小总耗时}

初值只有一个可达状态： $dp[0]=0$ （零个任务、零资源），其余都是无穷大。

处理第 $i$ 个任务时，对每个可达的 $r$ ，分别尝试它的两套配置：

dp'[r+c_1] = \min\left(dp'[r+c_1],\ dp[r]+t_1\right),\qquad dp'[r+c_2] = \min\left(dp'[r+c_2],\ dp[r]+t_2\right)

注意两件事：

必须用一张新表 $dp'$ 。如果就地更新，同一任务的另一套配置可能又从“刚被这个任务更新过的状态”转移一次，等于把这个任务选了两遍。
初值只有 $dp[0]$ 可达，这正好表达了“每个任务都必须选一套”，不会出现“跳过某个任务”的情况。

所有任务处理完后， $dp[r]$ 就是“正好用掉 $r$ 资源”时的最小耗时。题目要求资源不超过 $C$ ，所以答案在 $r=0,1,\dots,C$ 里按 (耗时, r) 取最小——从小到大扫描、只在严格更小时更新，就自动保住了“耗时相同取资源更少”的规则：

best_time, best_cost = float('inf'), 0
for r in range(C + 1):
    if dp[r] < best_time:      # 严格小于，同分时保留更小的 r
        best_time, best_cost = dp[r], r

复杂度 $O(nC)$ ， $n\le100$ 、 $C\le1000$ ，最多 $2\times10^5$ 次转移，非常轻松。

第四步：把两级目标编码成一个整数

第三步已经正确，但它把“耗时”和“资源”分开保存，最后还要再扫一遍、再写一次比较。可以用一个整数同时表达两级目标：

\text{score} = \text{总耗时}\times \text{BIG} + \text{实际资源},\qquad \text{BIG}=C+1

因为实际资源最多是 $C$ ，永远小于 BIG，所以 score 的“低位”就是资源，“高位”就是耗时：

耗时更小的方案，score 至少小 BIG，一定赢；
耗时相同时，score 的差就是资源的差，资源小的赢。

这样两级比较变成一次整数比较，DP 转移写成：

dp[r+c] = \min\left(dp[r+c],\ dp[r] + t\times\text{BIG} + c\right)

最后答案就是 min(dp)，再用整除和取余反解：

\text{耗时} = \left\lfloor \frac{\text{score}}{\text{BIG}} \right\rfloor,\qquad \text{资源} = \text{score} \bmod \text{BIG}

三个细节：

BIG 必须取 $C+1$ ，不能取 $C$ 。 若 BIG = C，当资源恰好等于 $C$ 时会“进位”到耗时位，反解出的耗时凭空多 1。
反解不用向上取整。 这里的 score 是“耗时×BIG + 资源”，资源是非负的，直接整除即可；这与 P5311 里“减去惩罚”的编码不同。
输出的是资源，不是剩余。 剩余资源要单独算 C - 资源。

完整代码实现

"""
P5346. 双配置训练任务的最优资源调度 - 带两个目标的一维 DP

输入格式：
- 第 1 行：两个整数 n、C；
- 接下来 n 行：每行四个正整数 c1、t1、c2、t2。

输出格式：
- 一行三个整数：最小总耗时、该方案实际消耗的资源、剩余资源。

时间复杂度：O(n * C * 2)
空间复杂度：O(C)
"""

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    capacity = int(next(it))

    # BIG 要比任何可能的资源消耗都大，这样 score 的高位是耗时、
    # 低位是资源，反解时整除和取余不会互相进位。
    big = capacity + 1

    # dp[r] = 恰好用掉 r 点资源时的最小编码分数，None 表示不可达
    dp = [None] * (capacity + 1)
    dp[0] = 0  # 零个任务、零资源

    for _ in range(n):
        c1 = int(next(it))
        t1 = int(next(it))
        c2 = int(next(it))
        t2 = int(next(it))

        # 用一张新表：第 i 个任务只能从“处理完前 i-1 个任务”的状态转移一次。
        # 若在原表上就地更新，同一任务的另一套配置可能被重复使用。
        next_dp = [None] * (capacity + 1)

        for used in range(capacity + 1):
            base = dp[used]
            if base is None:
                continue  # 这个资源量凑不出来

            # 每组恰好两个物品：配置 1 与配置 2，各试一次
            for cost, time in ((c1, t1), (c2, t2)):
                new_used = used + cost
                if new_used > capacity:
                    continue  # 超出资源上限

                # 耗时放高位、资源放低位：耗时优先，同耗时再比资源
                candidate = base + time * big + cost
                if next_dp[new_used] is None or candidate < next_dp[new_used]:
                    next_dp[new_used] = candidate

        dp = next_dp

    # 资源上限是“不超过 C”，所以在所有可达状态里挑分数最小的
    best = None
    for used in range(capacity + 1):
        if dp[used] is not None and (best is None or dp[used] < best):
            best = dp[used]

    if best is None:
        # 题目保证至少存在一种合法选择，这里只是防御性处理
        print(-1)
        return

    # 反解：score = 耗时 * big + 资源，且资源 <= C < big
    total_time = best // big
    total_cost = best % big
    print(total_time, total_cost, capacity - total_cost)


if __name__ == "__main__":
    solve()

示例推演

示例 1

$n=3$ 、 $C=10$ ，三个任务的配置是：

任务	配置 1 $(c_1,t_1)$	配置 2 $(c_2,t_2)$
1	(4, 5)	(2, 3)
2	(3, 4)	(5, 2)
3	(1, 2)	(2, 2)

一共 $2^3=8$ 种方案，全部列出来（超预算的标出）：

任务 1	任务 2	任务 3	总资源	总耗时	是否合法
1	1	1	4+3+1=8	5+4+2=11	合法
1	1	2	4+3+2=9	5+4+2=11	合法
1	2	1	4+5+1=10	5+2+2=9	合法
1	2	2	4+5+2=11	—	超预算
2	1	1	2+3+1=6	3+4+2=9	合法
2	1	2	2+3+2=7	3+4+2=9	合法
2	2	1	2+5+1=8	3+2+2=7	合法
2	2	2	2+5+2=9	3+2+2=7	合法

最小耗时是 $7$ ，有两个方案达到：资源 $8$ 和资源 $9$ 。按并列规则取资源更少的 $8$ ，剩余 $10-8=2$ ，输出：

7 8 2

用编码验证（BIG = 11）：

方案 (2,2,1)： $7\times11+8=85$ ；
方案 (2,2,2)： $7\times11+9=86$ 。

$85<86$ ，同耗时下资源 $8$ 胜出。反解： $85\div11=7$ ， $85\bmod11=8$ ，正是 $(7,8)$ 。

示例 2

$n=1$ 、 $C=1$ ，唯一任务是 $(c_1,t_1)=(1,5)$ 、 $(c_2,t_2)=(2,3)$ 。

配置 2 需要 2 点资源，超过上限 $1$ ，只有配置 1 合法：

5 1 0

这也说明：耗时更小的配置不一定能选，资源约束优先。

示例 3

$n=2$ 、 $C=5$ ：

任务	配置 1 $(c_1,t_1)$	配置 2 $(c_2,t_2)$
1	(3, 4)	(2, 6)
2	(2, 5)	(4, 1)

四种组合：

组合	总资源	总耗时	是否合法
1,1	3+2=5	4+5=9	合法
1,2	3+4=7	—	超预算
2,1	2+2=4	6+5=11	合法
2,2	2+4=6	—	超预算

最小耗时是 $9$ （方案 1,1），资源恰好用满 $5$ ，剩余 $0$ ：

9 5 0

方案 (2,1) 的资源更少（ $4$ ），但耗时 $11$ 更大——先比耗时，再比资源，顺序不能反。

示例 4

$n=3$ 、 $C=1000$ ，资源非常充足，每个任务可以独立选耗时更小的配置：

任务	配置 1	配置 2	选择	资源	耗时
1	(10, 20)	(5, 25)	配置 1（耗时 20 < 25）	10	20
2	(3, 15)	(4, 15)	耗时相同，取资源少的配置 1	3	15
3	(6, 7)	(2, 12)	配置 1（耗时 7 < 12）	6	7

总耗时 $20+15+7=42$ ，总资源 $10+3+6=19$ ，剩余 $1000-19=981$ ：

42 19 981

任务 2 是本题并列规则的典型：两套配置耗时都是 $15$ ，此时必须选资源更少的 $(3,15)$ 。如果只看耗时、两套里随便挑一套，总资源会变成 $20$ ，输出就成了 42 20 980，与正确答案差 1。

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举所有选择	$O(2^n\cdot n)$	$O(n)$	$n=100$ 时 $2^{100}$ ，不可行
按资源 DP + 最后两级比较	$O(nC)$	$O(C)$	正确；末尾还要按 `(耗时, 资源)` 扫一遍
按资源 DP + 整数编码（本题）	$O(nC)$	$O(C)$	两级目标合成一次比较，答案直接取 `min(dp)`

本题 $n\le100$ 、 $C\le1000$ ，转移次数约 $2\times10^5$ ，在 Python 里几毫秒就能跑完。

每组 $k$ 套配置：把内层 for cost, time in ((c1,t1),(c2,t2)) 换成遍历 $k$ 个配置即可，复杂度变为 $O(nCk)$ 。
两种以上资源：状态要多一维（如 $dp[r_1][r_2]$ ），复杂度变成 $O(nC_1C_2)$ ，做法与 P5311 的二维背包一致。
要求输出具体方案：再开一张表记录每个状态是从哪个 $(r,\text{配置})$ 转移来的，最后从最优状态倒推。
$C$ 很大（如 $10^9$ ）：按资源做 DP 不可行。此时可以改成按耗时做 DP（ $dp[t]$ = 达到耗时 $t$ 的最小资源），或者用 Lagrangian 松弛（给资源加一个价格）来逼近，但精确解在一般情况下是 NP 难的。
任务有先后依赖：如果某些任务必须在另一些之前完成，就不再是简单分组背包，需要把依赖关系建成 DAG，在拓扑序上做 DP。

双配置训练任务的最优资源调度

P5346. 双配置训练任务的最优资源调度

题目描述

输入格式

输出格式

示例

示例 1

示例 2

示例 3

示例 4

解题思路

第一步：理解问题本质

第二步：暴力解法

第三步：优化解法——按资源做 DP（每个任务必须选一次）

第四步：把两级目标编码成一个整数

完整代码实现

示例推演

示例 1

示例 2

示例 3

示例 4

复杂度分析

易错点总结

1. 把“必须选一套”写成“可以都不选”

2. 就地更新导致同一任务被选两次

3. 只记录最小耗时，丢掉资源

4. `BIG` 取成 $C$

5. 输出剩余资源时算错基准

6. 把两级目标的优先级弄反

7. 不可行输入没有兜底

扩展思考

相关题目