【动态规划】机器分配

题目

1013. 机器分配 - AcWing题库

---

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

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

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

求出最大盈利值。

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

输入格式

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

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

输出格式

第一行输出最大盈利值；

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

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

数据范围

$1 \le N \le 10$ ,
$1 \le M \le 15$

输入样例：

3 3
30 40 50
20 30 50
20 25 30

输出样例：

70
1 1
2 1
3 1

解题

方法一：动态规划

思路

本题可以看作是一个分组背包问题，其中 $M$ 台相同的高效设备代表背包的容量为 $M$ ， $N$ 个分公司代表有 $N$ 个分组，每个分组中固定有 $M$ 个物品，对于每个物品来说，下标 $1\sim M$ 是其体积，盈利是其价值。直接代入分组背包问题模板即可得到第一问答案最大盈利值。

第二问是完全背包问题求具体方案，参考【动态规划】背包问题求具体方案求解。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        int c = m, s = c;
        int[][] w = new int[n + 1][s + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                in.nextToken();
                w[i][j] = (int) in.nval;
            }
        }
        int[][] f = new int[n + 1][c + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= c; ++j) {
                f[i][j] = f[i - 1][j];
                for (int k = 0; k <= s; ++k) {
                    if (k <= j) f[i][j] = Math.max(f[i][j], f[i - 1][j - k] + w[i][k]);
                }
            }
        }
        System.out.println(f[n][c]);
        int[] sels = new int[n + 1];
        int j = c;
        for (int i = n; i >= 1; --i) {
            for (int k = 0; k <= s; ++k) {
                if (k <= j && f[i][j] == f[i - 1][j - k] + w[i][k]) {
                    sels[i] = k;
                    j -= k;
                    break;
                }
            }
        }
        for (int i = 1; i <= n; ++i) System.out.println(i + " " + sels[i]);
    }
}