【最新华为OD机试E卷】最大报酬(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷目录，全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目敬请期待

最新华为OD机试目录: https://www.nowcoder.com/share/jump/3022116661724989756887

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

💰 最大报酬

问题描述

小明每周上班都会拿到自己的工作清单，工作清单内包含 项工作，每项工作都有对应的耗时时间（单位 h）和报酬，工作的总报酬为所有已完成工作的报酬之和。请你帮小明安排工作，保证小明在指定的工作时间内工作收入最大化。

输入格式

第一行包含两个正整数 和 。 代表工作时长（单位 h）， 代表工作数量。 接下来 行，每行包含两个整数 和 。 代表第 项工作消耗的时长（单位 h）， 代表第 项工作的报酬。

输出格式

输出一个整数，表示小明在指定工作时长内可获得的最大报酬。

样例输入

40 3
20 10
20 20
20 5

样例输出

30

样例解释

无

数据范围

• 
• 
• 
• 为整数

题解

这道题目本质上是一个 0-1 背包问题。每项工作可以看作是一个物品，工作时长就是物品的重量，报酬就是物品的价值。我们需要在有限的时间（背包容量）内，选择一些工作（物品）来获得最大的报酬（价值）。

解决这个问题的关键在于使用动态规划。定义一个二维数组 dp[i][j]，表示前 i 个工作在 j 小时内能获得的最大报酬。状态转移方程如下：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]] + w[i])  if j >= t[i]
dp[i][j] = dp[i-1][j]                               if j < t[i]

这个方程的含义是：对于第 i 个工作，有两种选择：做或不做。如果不做，那么最大报酬就是前 i-1 个工作在 j 小时内的最大报酬。如果做，那么需要先腾出这个工作所需的时间，然后加上这个工作的报酬。

算法的主要步骤如下：

1. 初始化 dp 数组，所有元素设为 0。
2. 遍历每个工作。
3. 对于每个工作，遍历从该工作所需时间到总时间 T 的每个时间点。
4. 对于每个时间点，计算做这个工作和不做这个工作两种情况下的最大报酬，取较大值。
5. 最终答案就是 。

在实际实现中，可以使用滚动数组来优化空间复杂度到 O(T)。这种优化不会改变时间复杂度，但可以大大减少内存使用。

参考代码

• Python

# 读取输入
T, n = map(int, input().split())
jobs = [list(map(int, input().split())) for _ in range(n)]

# 初始化dp数组
dp = [0] * (T + 1)

# 动态规划过程
for t, w in jobs:
    for j in range(T, t - 1, -1):
        # 状态转移：选择当前工作或不选择
        dp[j] = max(dp[j], dp[j - t] + w)

# 输出结果
print(dp[T])

• C

#include <stdio.h>
#include <string.h>

#define MAX_T 1