工作安排 - 华为OD统一考试(E卷)
2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集
题目描述
小明每周上班都会拿到自己的工作清单，工作清单内包含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
题解
分析
这道题属于动态规划问题，类似于经典的0/1背包问题，即在限定的资源（工作时长）下，如何选择工作使得报酬最大化。每项工作都有消耗的时间和对应的报酬，要求在有限的总工作时间内，选择一些工作使得获得的总报酬最大。
思路
可以将每项工作看作背包中的物品，每项工作消耗的时间就是物品的重量，工作的报酬就是物品的价值。我们要在给定的工作时长限制内，选出能够使得报酬最大的工作组合。
具体来说，动态规划的思路如下：
状态定义：
dp[i]表示在工作时长为i时，能够获得的最大报酬。状态转移：
对于每个工作
(t, w)，表示该工作消耗时间t并获得报酬w。我们需要决定是否选择该工作：
- 如果不选择，则
dp[cap]保持不变。- 如果选择，则
dp[cap] = max(dp[cap], dp[cap - t] + w)。从后往前遍历
dp数组，确保每个工作只能被选择一次（类似 0/1 背包问题）。初始化：
dp[0] = 0表示工作时长为 0 时的最大报酬为 0，其他dp初始化为 0，因为我们假设初始时还未完成任何工作。结果：
- 最终结果就是
dp数组中的最大值，表示在给定的总工作时长T内能获得的最大报酬。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取T和n的值
i剩余60%内容，订阅专栏后可继续查看/也可单篇购买
华为OD机试题库题解2024 文章被收录于专栏
华为OD机考（CDE卷）题库（绝对都是原题），帮助你上岸华为（已经不少小伙伴成功上岸）。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题，随时解答。
投递华为等公司10个岗位 >