一、题目描述
小明每周上班都会拿着自己的工作清单，工作清单内包含n项工作，每项工作都有对应的耗时时长（单位h）和报酬，工作的总报酬为所有已完成工作的报酬之和。那么请你帮小明安排一下工作，保证小明在指定的工作时间内完成工作收入最大化。
二、输入描述
输入的第一行为两个正整数T，n。
T代表工作时长（单位h，0 < T <100000），n代表工作数量（0 < n <= 3000）。
接下来是n行，每行包含两个整数t，w。
t代表该项工作消耗的时长（单位h,t > 0），w代表该项工作的报酬。
三、输出描述
输出小明指定工作时长内可获得的最大报酬。
四、解题思路
- 读取输入的工作时长 T 和工作数量 n；
- 创建两个数组 timeArr 和 workArr，用于存储每项工作的时长和报酬；
- 读取每项工作的时长和报酬，并将其存入对应的数组中；
- 创建一个二维数组 dp，其中 dp[i][j] 表示在前 i 项工作中，使用时长不超过 j 的情况下的最大报酬；
- 初始化 dp 数组的第一行和第一列为0，表示不选择任何工作或不使用任何时长时的最大报酬为0；
- 使用动态规划的思想，遍历所有工作和时长的组合，更新 dp 数组；如果第 i 项工作的时长小于等于当前时长 j，则可以选择该工作，更新 dp[i][j] 为不选择该工作和选择该工作的两种情况中的最大报酬；
- 遍历结束后，dp[n][T] 即为小明在指定工作时长内可获得的最大报酬；
- 输出最大报酬；
五、Python算法源码
def calculate_max_income(T, n, works):
time_arr = [] # 存储每项工作的时长
work_arr = [] # 存储每项工作的报酬
for i in range(n):
t, w = works[i]
time_arr.append(t)
work_arr.append(w)
dp = [[0] * (T + 1) for _ in range(n + 1)] # 创建二维数组dp，用于存储最大报酬
for i in range(1, n + 1):
for j in range(1, T + 1):
if time_arr[i - 1] <= j:
# 如果第i项工作的时长小于等于当前时长j，可以选择该工作
# 更新dp[i][j]为不选择该工作和选择该工作的两种情况中的最大报酬
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time_arr[i - 1]] + work_arr[i - 1])
return dp[n][T]
六、效果展示
1、输入
60 4
20 10
20 20
30 30
20 15
2、输出
50
3、说明
一共60小时，4行数据，如果组合才能使工作收入最大化呢？
20 + 30 = 50。
🏆下一篇：华为OD机试真题 Python 实现【相对开音节】【2022Q4 100分】，附详细解题思路
🏆本文收录于，华为OD机试（Python）真题（A卷+B卷）
每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。