侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【动态规划】机器分配

GabrielxD
2023-02-19 / 0 评论 / 0 点赞 / 77 阅读 / 718 字
温馨提示:
本文最后更新于 2023-02-19,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1013. 机器分配 - AcWing题库


总公司拥有 MM相同 的高效设备,准备分给下属的 NN 个分公司。

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

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

求出最大盈利值。

分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数 MM

输入格式

第一行有两个数,第一个数是分公司数 NN ,第二个数是设备台数 MM

接下来是一个 N×MN \times M 的矩阵,矩阵中的第 ii 行第 jj 列的整数表示第 ii 个公司分配 jj 台机器时的盈利。

输出格式

第一行输出最大盈利值;

接下 NN 行,每行有 22 个数,即分公司编号和该分公司获得设备台数。

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

数据范围

1N101 \le N \le 10 ,
1M151 \le M \le 15

输入样例:

3 3
30 40 50
20 30 50
20 25 30

输出样例:

70
1 1
2 1
3 1

解题

方法一:动态规划

思路

本题可以看作是一个分组背包问题,其中 MM相同的高效设备代表背包的容量为 MMNN 个分公司代表有 NN 个分组,每个分组中固定有 MM 个物品,对于每个物品来说,下标 1M1\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]);
    }
}
0

评论区