机器分配（未解决）

题目 机器分配

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

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

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

求出最大盈利值。

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

输入格式

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

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

输出格式

第一行输出最大盈利值；

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

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

数据范围

1≤N≤10,1≤M≤15

输入样例：

3 3
30 40 50
20 30 50
20 25 30

输出样例：

70
1 1
2 1
3 1

样例解读：

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

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

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

动态规划求状态转移路径

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

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

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

具体如下图所示：

image-6f616917

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

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

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

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

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

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

如下图所示：

image-4c28538d

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

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

代码实现

#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-刷题理模型 ➡️ 周氏背包九讲