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

算法刷题2年前 (2023)更新江南白衣

全网最全面的华为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]);
    }
}