Loading...
百度&必应权4, 日IP8000. 查看详情
自助收录

2023年华为OD机考真题:工作安排

算法刷题1年前 (2023)更新 江南白衣
380 0 0
2023年华为OD机考真题:工作安排

全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。

真题库:https://www.yuque.com/codernav.com/od

题目:工作安排
知识点循环数组贪心动态规划
时间限制:1s 空间限制:32MB 限定语言:不限
题目描述:
小明每周上班都会拿到自己的工作清单,工作清单内包含n项工作,每项工作都有对应的耗时时长(单位h)和报酬,工作的总报酬为所有已完成工作的报酬之和。那么请你帮小明安排一下工作,保证小明在指定的工作时间内工作收入最大化。
输入描述:
输入的第一行为两个正整数T,n。T代表工作时长(单位h,0 < T < 100000),n代表工作数量(1 < n ≤ 3000)。
接下来是n行,每行包含两个整数t,w。t代表该项工作消耗的时长(单位h,t > 0),w代表该项工作的报酬。
输出描述:
输出小明指定工作时长内工作可获得的最大报酬。
示例1
输入:
40 3
20 10
20 20
20 5
输出:
30
解题思路:
博主使用了动态规划,大家也可以用其方法。
关键是新建一个长度为T+1的数组。然后动态获取各指定时间内的最大报酬。

代码实现一:

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 工作安排
 * @Description 小明每周上班都会拿到自己的工作清单,工作清单内包含n项工作,每项工作都有对应的耗时时长(单位h)和报酬,工作的总报酬为所有已完成工作的报酬之和。
 * 那么请你帮小明安排一下工作,保证小明在指定的工作时间内工作收入最大化。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/14
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int n = sc.nextInt();
        int[] times = new int[n];
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            times[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }
        int res = handle(T, times, values);
        System.out.println(res);
    }

    /**
     * 动态规划
     *
     * @param T      工作时长
     * @param times  任务工作数组
     * @param values 任务报酬数组
     * @return
     */
    public static int handle(int T, int[] times, int[] values) {
        int[] dp = new int[T + 1];    //相当于各个时间所能做的最大报酬
        for (int i = 0; i < times.length; i++) {
            for (int j = T; j >= times[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - times[i]] + values[i]);
            }
        }
        return dp[T];
    }
}

代码实现二:

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 工作安排
 * @Description 小明每周上班都会拿到自己的工作清单,工作清单内包含n项工作,每项工作都有对应的耗时时长(单位h)和报酬,工作的总报酬为所有已完成工作的报酬之和。
 * 那么请你帮小明安排一下工作,保证小明在指定的工作时间内工作收入最大化。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/14
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        int n = scanner.nextInt();
        int[] w = new int[n];
        int[] val = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
            val[i] = scanner.nextInt();
        }
        int[][] v = new int[n + 1][t + 1];
        for (int i = 1; i < v.length; i++) {
            for (int j = 0; j < v[0].length; j++) {
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                }
            }
        }
        System.out.println(v[n][t]);
    }
}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...