---
title: "机器分配（未解决）"
created: 2025-11-28
tags:
  - 算法
---

# 机器分配（未解决）

## 题目 [机器分配](https://www.cnblogs.com/littlehb/p/15717260.html)

总公司拥有 M 台 **相同** 的高效设备，准备分给下属的 N 个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这M台设备才能使国家得到的盈利最大？

求出最大盈利值。

**分配原则**：每个公司有权获得任意数目的设备，但总台数不超过设备数 M。

**输入格式**

第一行有两个数，第一个数是分公司数 N，第二个数是设备台数 M；

接下来是一个 N×M的矩阵，矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。

**输出格式**

第一行输出最大盈利值；

接下 N行，每行有 2 个数，即分公司编号和该分公司获得设备台数。

答案不唯一，输出任意合法方案即可。

**数据范围**

1≤N≤10,1≤M≤15

**输入样例**：

```text
3 3
30 40 50
20 30 50
20 25 30
```

**输出样例**：

```text
70
1 1
2 1
3 1
```

**样例解读**：

```text
3 3
30 40 50
20 30 50
20 25 30
```

3个公司，3台机器,**机器都是一样的，一样的，记住，一样的**,要不题意理解不明白~

- 1号公司
- 得到1台机器，30元
- 得到2台机器，40元
- 得到3台机器，50元
- 2号公司
- 得到1台机器，20元
- 得到2台机器，30元
- 得到3台机器，50元
- 3号公司
- 得到1台机器，20元
- 得到2台机器，25元
- 得到3台机器，30元

问，怎么分，使得国家的收益最大？

**答**:1号公司得到1台机器，2号公司得到1台机器，3号公司得到1台机器，就是30+20+20=70,此时国家利益最大。

## 思路分析

本题乍一看很像是 **背包DP**，为了转换成 **背包DP** 问题，我们需要对里面的一些叙述做出 **等价变换**

**每家公司** 我们可以看一个 **物品组**，又因为 **所有公司** 最终能够被分配的 **机器数量** 是固定的

**思路转换**

**① 对于分给第i个公司的不同机器数量可以分别看作是一个物品组内的物品数量。**

**② 物品k的含义：分给第i个公司k台机器**

**③ 物品k的体积：因为一个机器算一个，所以体积也是k**

**④ 物品k的价值：wk**

直接上 **分组背包** 的 **闫氏DP分析法**

![[image-ac7e3060.png]]

初始状态 ：f[0][0]

目标状态 ：f[N][M]

#### 动态规划求状态转移路径

这里介绍一个从 **图论** 角度思考的方法

**动态规划** 本质是在一个 **拓扑图** 内找 **最短路**

可以把每个 **状态**f[i][j]看作一个 **点**，**状态的转移** 看作一条 **边**，把 **状态的值** 理解为 **最短路径长**

具体如下图所示：

![[image-6f616917.png]]

对于 **点** f[i][j] 来说，他的 **最短路径长** 是通过所有到他的 **边** 更新出来的

更新 **最短路** 的 **规则** 因题而已，本题的 **更新规则** 是

f(i,j)=max(f(i−1,j−vi))+wi

最终，我们会把从 **初始状态**（起点）到 **目标状态** （终点）的 **最短路径长** 更新出来

随着这个更新的过程，也就在整个 **图** 中生成了一颗 **最短路径树**

该 **最短路径树** 上 **起点** 到 **终点** 的 **路径** 就是我们要求的 **动态规划的状态转移路径**

如下图所示：

![[image-4c28538d.png]]

那么 **动态规划求状态转移路径** 就变成了在 **拓扑图** 中找 **最短路径** 的问题了

可以直接沿用 **最短路** 输出路径的方法就可以找出 **状态的转移**

## 代码实现

```cpp
#include <iostream>

using namespace std;

const int N = 20;

int n, m;

int w[N][N];

int f[N][N];

int path[N], cnt;

void dfs(int i, int j)

{

    if (!i) return;

    //寻找当前状态f[i][j]是从上述哪一个f[i-1][k]状态转移过来的

    for (int a = 0; a <= j; ++ a)

    {

        if (f[i - 1][j - a] + w[i][a] == f[i][j])

        {

            path[cnt ++ ] = a;

            dfs(i - 1, j - a);

            return;

        }

    }

}

int main()

{

    //input

    cin >> n >> m;

    for (int i = 1; i <= n; ++ i)

        for (int j = 1; j <= m; ++ j)

            cin >> w[i][j];

    //dp

    for (int i = 1; i <= n; ++ i)

        for (int j = 1; j <= m; ++ j)

            for (int k = 0; k <= j; ++ k)

                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);

    cout << f[n][m] << endl;

    //find path

    dfs(n, m);

    for (int i = cnt - 1, id = 1; i >= 0; -- i, ++ id)

        cout << id << " " << path[i] << endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[有依赖+多重（未解决）金明的预算方案|有依赖+多重（未解决）金明的预算方案]] 🏠 [[00-刷题理模型]] ➡️ [[周氏背包九讲|周氏背包九讲]]