工作安排 - 华为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的值int T = sc.nextInt();int n = sc.nextInt();// 初始化dp数组int[] dp = new int[T + 1];// 循环读取工作消耗的时长t和工作的报酬for (int i = 0; i < n; i++) {int t = sc.nextInt();int w = sc.nextInt();// 动态规划,从后往前遍历以避免重复使用for (int cap = T; cap >= t; cap--) {dp[cap] = Math.max(dp[cap], dp[cap - t] + w);}}// 找到dp数组中的最大值,即为答案int result = 0;for (int x : dp) {result = Math.max(result, x);}// 输出结果System.out.println(result);}
}
Python
# T 工作时长, n 工作数量
T, n = map(int, input().split())# 初始化dp数组
dp = [0] * (T + 1)# 循环读取工作消耗的时长t和工作的报酬
for _ in range(n):t, w = map(int, input().split())# 动态规划,从后往前遍历以避免重复使用for cap in range(T, t - 1, -1):dp[cap] = max(dp[cap], dp[cap - t] + w)# 输出结果
print(max(dp))
C++
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {int T, n;cin >> T >> n;vector<int> dp(T + 1, 0);int t, w;for (int i = 0; i < n; i++) { // 循环读取工作消耗的时长t和工作的报酬cin >> t >> w;for (int cap = T; cap >= t; cap--) { // 动态规划,从后往前遍历以避免重复使用dp[cap] = max(dp[cap], dp[cap - t] + w);}}int result = 0;for (int x: dp) result = max(result, x);cout << result << endl;return 0;
}
整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏