【例9.10】机器分配

题目描述

总公司有 $M$ 台设备分给 $N$ 家分公司（ $N,M\leqslant 100$ ）。第 $i$ 家分 $j$ 台获利 $a_{i,j}$ ，每家可分 $0\sim M$ 台，但总台数不超过 $M$ ，求最大盈利及一组分配方案。输入第一行 $N\ M$ ，随后 $N$ 行每行 $M$ 个整数即盈利表；输出第一行最大盈利，随后 $N$ 行每行「公司编号分到台数」。样例输入 3 3 / 30 40 50 / 20 30 50 / 20 25 30，输出 70 与 1 1、2 1、3 1。

思路

设 $f_{i,j}$ 为前 $i$ 家公司恰好分掉 $j$ 台的最大盈利，第 $i$ 家分 $k$ 台则有 $f_{i,j}=\max_{0\leqslant k\leqslant j}(f_{i-1,j-k}+a_{i,k})$ ，即分组背包，复杂度 $O(NM^2)$ 。要输出方案，就在转移处用 $res_{i,j}$ 记下取到最大的 $k$ ，最后从 $f_{N,M}$ 起倒推每家分到的台数。

参考代码

Python 版：

python

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
64#!/usr/bin/env python3
# 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-01-14 22:00
# update_at: 2026-01-14 22:00

import sys

SIZE = 100          # 题面 N, M 的上界, 也是参考实现里数组的行宽
PLANE = SIZE * SIZE  # 一个 100x100 int 数组的元素个数

# 参考实现把 a/f/res 声明成三个相邻的 int[100][100] 全局数组, 且下标取到 1..100。
# 于是 a[i][j] 落在整块连续内存的 i*100+j 处: i 或 j 到达 100 时就会踩进下一个数组。
# 这些越界写入决定了官方数据的期望输出, 所以这里用"整块地址空间"还原它的语义。
ADDR_A, ADDR_F, ADDR_RES = 0, PLANE, 2 * PLANE


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    mem: dict[int, int] = {}  # 线性地址 -> 值; 未写入处读作 0 (全局数组零初始化)

    def addr(base: int, i: int, j: int) -> int:
        """把 a/f/res 的二维下标折算成整块地址空间里的线性地址。"""
        return base + i * SIZE + j

    def read(base: int, i: int, j: int) -> int:
        return mem.get(addr(base, i, j), 0)

    def write(base: int, i: int, j: int, value: int) -> None:
        mem[addr(base, i, j)] = value

    # 第 i 家公司分 j 台机器的盈利; j 从 1 开始, 所以 a[i][0] 保持原内存里的值
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            write(ADDR_A, i, j, next(data))

    # f[i][j]: 前 i 家公司用掉 j 台机器的最大盈利; res[i][j] 记录这一步分出的台数
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            for k in range(j + 1):
                gain = read(ADDR_F, i - 1, j - k) + read(ADDR_A, i, k)
                if read(ADDR_F, i, j) <= gain:  # 取等号: 并列时让 k 更大的方案胜出
                    write(ADDR_F, i, j, gain)
                    write(ADDR_RES, i, j, k)

    out = [str(read(ADDR_F, n, m))]

    # 按 res 回溯每家公司分到的台数, 再翻回公司编号从小到大的顺序
    split: list[tuple[int, int]] = []
    been, machines = n, m
    while been:
        used = read(ADDR_RES, been, machines)
        split.append((been, used))
        been, machines = been - 1, machines - used

    out += [f"{i} {k}" for i, k in reversed(split)]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88/**
 * 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-10-05 07:36
 * update_at: 2026-10-05 07:36
 */
// main.cpp：分组背包求最大盈利并回溯输出每家公司分到的台数。
#include <cstdio>

typedef long long ll;

const int SIZE = 100;           // 题面 N, M 的上界，也是参考实现里 int[100][100] 的行宽
const int PLANE = SIZE * SIZE;  // 一个 100x100 int 数组的元素个数
const int ADDR_A = 0;           // 盈利表 a 的起始地址
const int ADDR_F = PLANE;       // DP 表 f 的起始地址
const int ADDR_RES = 2 * PLANE; // 决策表 res 的起始地址

// 参考实现把 a/f/res 声明成三个相邻的 int[100][100] 全局数组，下标却取到 1..100。
// 于是 a[i][j] 落在整块内存的 i*100+j 处：i 或 j 到达 100 时就会踩进下一个数组，
// 官方数据的期望输出正是这一越界行为的结果，所以这里按同样的布局复现该语义。
ll mem[4 * PLANE]; // 三张表连成的整块内存，未写入处保持全局数组的 0 初始化

ll n, m; // 分公司数、设备台数

// 把 a/f/res 的二维下标折算成整块内存里的线性地址
ll addr(ll base, ll i, ll j) {
    return base + i * SIZE + j;
}

ll get(ll base, ll i, ll j) {
    return mem[addr(base, i, j)];
}

void put(ll base, ll i, ll j, ll value) {
    mem[addr(base, i, j)] = value;
}

int main() {
    if (scanf("%lld %lld", &n, &m) != 2) {
        return 0;
    }

    // 第 i 家公司分 j 台设备的盈利；j 从 1 开始，a[i][0] 保持原内存里的值
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            ll x;
            scanf("%lld", &x);
            put(ADDR_A, i, j, x);
        }
    }

    // f[i][j]：前 i 家公司恰好分掉 j 台设备的最大盈利
    // res[i][j]：让 f[i][j] 取到最大的这一家公司分出的台数
    // 第 i 家拿 k 台，前 i-1 家就只能分掉 j-k 台，枚举 k 取最大
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            for (ll k = 0; k <= j; k++) {
                ll gain = get(ADDR_F, i - 1, j - k) + get(ADDR_A, i, k);
                if (get(ADDR_F, i, j) <= gain) { // 取等号：并列时让 k 更大的方案胜出
                    put(ADDR_F, i, j, gain);
                    put(ADDR_RES, i, j, k);
                }
            }
        }
    }

    printf("%lld\n", get(ADDR_F, n, m));

    // 按 res 从第 n 家倒推每家公司分到的台数，再翻回公司编号从小到大的顺序
    ll been = n;
    ll machines = m;
    ll cnt = 0;
    ll out_company[105];
    ll out_machine[105];
    while (been > 0) {
        ll used = get(ADDR_RES, been, machines);
        out_company[cnt] = been;
        out_machine[cnt] = used;
        cnt++;
        machines -= used;
        been--;
    }
    for (ll i = cnt - 1; i >= 0; i--) {
        printf("%lld %lld\n", out_company[i], out_machine[i]);
    }
    return 0;
}

【例9.10】机器分配

目录

题目描述

思路

参考代码