1013 机器分配（多重与分组背包问题扩展）

灰太狼 2022-09-11 03:21 120阅读 0赞

**1. 问题描述：**

总公司拥有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  
来源：[https://www.acwing.com/problem/content/description/1015/][https_www.acwing.com_problem_content_description_1015]

**2. 思路分析：**

对于这种有相应情景的题目，我们一般是根据自己的理解将其抽象为具体的模型，由题目可知这道题目属于**选择性的组合问题**，对于这种没有选择顺序的组合问题我们想到背包问题的模型，可以发现这道题目类似于多重背包问题和分组背包的组合（每个公司可以看成是一个组，组内的物品可以选择一定的数量），我们可以借助于多重背包与分组背包的思路来解决这个问题，可以将机器看成是一个物品，机器的总数量看成是背包的容量，最大的盈利可以看成在背包容量最多能够装满的前提下能够获得的最大价值，因为最终需要求解出具体的方案所以我们可以定义一个二维数组或者二维列表dp（在逆着递推具体的方案的时候需要使用到上一个状态的值所以我们需要使用二维数组来记录下对应状态的值,，如果求解的是方案数目可以声明一个一维数组逆序遍历体积），其中dp\[i\]\[j\]表示前i家公司中已经分配j台机器能够获得的最大价值，类似于多重背包的枚举思路，我们可以使用三层循环枚举，第一层循环枚举所有的公司，第二层循环枚举机器数量（相当于是体积），第三层循环枚举第i家公司分配k台机器能够获得的最大价值，最终dp\[n\]\[m\]为当前n家公司分配机器数量不超过m能够获得的最大盈利；因为需要求解任何一个合法的方案，所以我们可以从dp\[n\]\[m\]倒着递推找到当前公司需要分配多少台机器才能从上一个状态到达当前的状态，可以使用一维数组或者列表记录下答案，最终递推到第一家公司就结束了。

**3. 代码如下：**

if __name__ == '__main__':
        n, m = map(int, input().split())
        dp = [[0] * (m + 1) for i in range(n + 1)]
        # w为每家公司分配的机器数量对应的盈利, 二维列表前面加上一行0并且每一行的最前面加上一个0这样下标可以从1开始
        w = [[0] * (m + 1)]
        for i in range(1, n + 1):
            w.append([0] + list(map(int, input().split())))
        for i in range(1, n + 1):
            for j in range(m + 1):
                # 枚举第i家公司分配k台机器能够获得的最大价值
                for k in range(j + 1):
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + w[i][k])
        print(dp[n][m])
        j = m
        res = [0] * (n + 1)
        # 逆序求解方案这样才可以从dp[n][m]逆推寻找上一个转移的合法方案
        for i in range(n, 0, -1):
            for k in range(0, j + 1):
                if dp[i][j] == dp[i - 1][j - k] + w[i][k]:
                    res[i] = k
                    j -= k
                    break
        for i in range(1, n + 1): print(i, res[i])

[https_www.acwing.com_problem_content_description_1015]: https://www.acwing.com/problem/content/description/1015/