2024华为OD试题及答案-A058-最大报酬

题目描述

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

输入描述

输入的第一行为两个正整数 T，n。
T 代表工作时长（单位 h， 0 < T < 1000000），
n 代表工作数量（ 1 < n ≤ 3000）。
接下来是 n 行，每行包含两个整数 t，w。
t 代表该工作消耗的时长（单位 h， t > 0），w 代表该项工作的报酬。

输出描述

输出小明指定工作时长内工作可获得的最大报酬。

用例

问题分析

输入

输出

• 小明在指定工作时长内工作可获得的最大报酬。

解题思路

这是一个典型的背包问题，可以使用动态规划来解决。

1. 初始化：创建一个大小为 T+1 的数组 dp，dp[i] 表示在工作时长为 i 时可以获得的最大报酬。
2. 动态规划：
   • 对每个工作 (t, w)：
     • 从后向前遍历工作时长 i（从 T 到 t），更新 dp[i] 的值。
     • 更新公式：dp[i] = max(dp[i], dp[i-t] + w)。
3. 结果：dp[T] 即为在最大工作时长 T 内可以获得的最大报酬。

伪代码

1. 初始化 dp 数组，大小为 T+1，所有元素初始为0。
2. 对每个工作 (t, w)，从 T 到 t 更新 dp 数组。
3. 输出 dp[T]。

接下来，我们分别用C++和Python来实现这个问题。

C++实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int T, n;
    cin >> T >> n;

    vector<int> dp(T + 1, 0);

    for (int i = 0; i < n; ++i) {
        int t, w;
        cin >> t >> w;
        for (int j = T; j >= t; --j) {
            dp[j] = max(dp[j], dp[j - t] + w);
        }
    }

    cout << dp[T] << endl;

    return 0;
}

Python实现

def main():
    import sys
    input = sys.stdin.read
    data = input().split()

    T = int(data[0])
    n = int(data[1])

    dp = [0] * (T + 1)

    index = 2
    for _ in range(n):
        t = int(data[index])
        w = int(data[index + 1])
        index += 2
        for j in range(T, t - 1, -1):
            dp[j] = max(dp[j], dp[j - t] + w)

    print(dp[T])

if __name__ == "__main__":
    main()

使用说明

• 将上述C++代码保存为max_reward.cpp，然后使用命令行编译和运行：

  g++ max_reward.cpp -o max_reward
  ./max_reward
  

  输入工作时长、工作数量以及每个工作的时长和报酬，并按回车键查看输出。

• 将上述Python代码保存为max_reward.py，然后使用命令行运行：

  python max_reward.py
  

  输入工作时长、工作数量以及每个工作的时长和报酬，并按回车键查看输出。

这两个程序将会读取输入的数据，计算并输出小明在指定工作时长内可以获得的最大报酬。