AcWing 1013. 机器分配

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1013. 机器分配原题链接简单

作者：

小呆呆 , 2020-01-10 17:00:33 , 所有人可见 , 阅读 1901

6

1

算法分析

此题是分组背包求具体方案问题

1、由于题目答案不唯一，输入任意合法方案即可
2、通过多重背包模版求出最大盈利值f[n][m]
3、求具体方案，由于每个公司可以分配不同数量的机器，因此从n遍历到1，假设k为当前公司分配的机器数量，则若满足f[i][j] == f[i - 1][j - k] + w[i][k]，其中f[i][j]为当前最优情况，则表示f[i][j]可以从f[i - 1][j - k]状态转移过来,输出当前k值

时间复杂度 $O(nm^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 11;
    static int M = 16;
    static int[][] w = new int[N][M];
    static int[][] f = new int[N][M];
    static int n;
    static int m;
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = reader.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for(int i = 1; i <= n;i++)
        {
            String[] s2 = reader.readLine().split(" ");
            for(int j = 1;j <= m;j++)
            {
                w[i][j] = Integer.parseInt(s2[j - 1]);
            }
        }
        for(int i = 1;i <= n;i++)
        {
            for(int j = 0;j <= m;j++)
            {
                for(int k = 0;k <= j;k++)
                {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k] + w[i][k]);
                }
            }
        }
        System.out.println(f[n][m]);

        int j = m;
        for(int i = n;i >= 1;i--)
        {   //选择k个机器
            for(int k = 0;k <= j;k ++)
            {
                if(f[i][j] == f[i - 1][j - k] + w[i][k])
                {
                    System.out.println(i + " " + k);
                    j -= k;
                    break;
                }
            }
        }
    }
}

14 评论

糖豆 2022-07-26 11:18

大佬，这道题到底是多重，还是分组啊？明明是多重就可以AC掉，为什么要说是分组背包呢？


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k <= j; k++) {
                int val = f[i - 1][j - k] + w[i][k];
                if (val > f[i][j]) {
                    f[i][j] = f[i - 1][j - k] + w[i][k];
                    path[i][j] = k;
                }
            }

DiveBackInTime 2022-01-22 21:13

还有，这个代码在别的网站上交上去直接编译错误了
http://ybt.ssoier.cn:8088/problem_show.php?pid=1266

DiveBackInTime 2022-01-22 21:00

if(f[i][j] == f[i - 1][j - k] + w[i][k])
                {
                    System.out.println(i + " " + k);
                    j -= k;
                    break;
                }

这一段有问题吧，i是倒过来做的啊，不应该拿个数组保存一下然后循环外输出吗

玛卡巴卡呀 2021-06-02 17:33

package dp;

import java.util.Scanner;

public class 机器分配 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int N = 100, n, m, w[][] = new int[N][N], f[][] = new int[N][N];
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                w[i][j] = scanner.nextInt();
            }
        }
        for (int i = n; i >= 1; i--) {// 循环个数
            for (int j = 0; j <= m; j++) {// 循环体积,体积无法判断大于等于某一个值直接用0
                for (int k = 0; k <= m; k++) {// 循环组内的每一个元素,组内有m个元素
                    f[i][j] = f[i + 1][j];
                    if (j >= k)
                        // 在这个题目中个数相当于体积，所以在优化的时候k<=j即可

                        f[i][j] = Math.max(f[i][j], f[i + 1][j - k] + w[i][k]);
                    // System.out.println(f[i][j]);
                }
            }

        }
        System.out.println(f[1][m]);

    }

}

玛卡巴卡呀 2021-06-02 17:35

逆着循环，为什么输出的结果是错误的呢？
但是如果改成下面的代码就是正确的，这是为什么啊，求大佬解答

for (int i = n; i >= 1; i--) {// 循环个数
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= j; k++) {
                    f[i][j= Math.max(f[i][j], f[i + 1][j - k] + w[i][k]);
                }
            }

        }