【华为OD-E卷-工作安排 100分（python、java、c++、js、c）】-EW帮帮网

微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

【华为OD-E卷-工作安排 100分（python、java、c++、js、c）】

题目

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

输入描述

输入的第一行为两个正整数 T，n。

T 代表工作时长（单位 h， 0 < T < 1000000）， n 代表工作数量（ 1 < n ≤ 3000）。接下来是 n 行，每行包含两个整数 t，w。

t 代表该工作消耗的时长（单位 h， t > 0），w 代表该项工作的报酬。

输出描述

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

用例

用例一：

输入：

输出：

python解法

解题思路：
这是一个经典的背包问题，题目可以理解为：

问题描述：给定一个最大时间限制
𝑇
T 和
𝑛
n 个工作任务，每个任务有耗时
𝑡
t 和权重
𝑤
w。要求在总时间不超过
𝑇
T 的前提下，选择一些任务使得权重和最大。
解决方法：
使用动态规划（DP）解决。
定义 dp[j] 表示在时间限制为
𝑗
j 时，可以获得的最大权重。
对于每个任务，根据其耗时
𝑡
t 和权重
𝑤
w，尝试更新当前时间限制内的最大权重。
更新时，从时间限制
𝑇
T 向下遍历，避免任务重复选择。
动态规划公式
初始状态：dp[0] = 0，即在时间限制为 0 时，权重为 0。
转移方程：dp[j] = max(dp[j], dp[j - t] + w)，即考虑是否选择当前任务。
遍历顺序：从时间限制
𝑇
T 到任务耗时
𝑡
t（倒序），确保每个任务只被选择一次。

# 输入最大时间限制 T 和任务数 n
T, n = map(int, input().split())

# 输入每个任务的耗时 t 和权重 w
jobs = [tuple(map(int, input().split())) for _ in range(n)]

# 初始化 DP 数组，dp[j] 表示时间限制为 j 时的最大权重
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)

# 输出在时间限制 T 内的最大权重
print(dp[T])

java解法

解题思路
这是一道经典的0-1 背包问题，需要在给定时间限制
𝑇
T 内选择一些任务，最大化总奖励。

问题分析：

有
𝑛
n 个任务，每个任务有耗时
𝑡
𝑖
𝑚
𝑒
𝑠
[
𝑖
]
times[i] 和奖励
𝑟
𝑒
𝑤
𝑎
𝑟
𝑑
𝑠
[
𝑖
]
rewards[i]。
总时间限制为
𝑇
T，要求在时间不超过
𝑇
T 的情况下，选择任务使得总奖励最大。
解决方法：

使用动态规划（DP）解决。
定义 dp[j] 表示在时间限制为
𝑗
j 时可以获得的最大奖励。
遍历每个任务，根据其耗时和奖励，更新当前时间限制内的最大奖励。
动态规划公式：

初始状态：dp[0] = 0，即在时间限制为 0 时，奖励为 0。
转移方程：dp[j] = max(dp[j], dp[j - time] + reward)，表示是否选择当前任务。
倒序遍历时间
𝑇
T 至
𝑡
𝑖
𝑚
𝑒
time，确保每个任务只被选择一次

import java.util.Scanner;

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();

        // 初始化任务耗时和奖励数组
        int[] times = new int[n];
        int[] rewards = new int[n];

        // 输入每个任务的耗时和奖励
        for (int i = 0; i < n; i++) {
            times[i] = sc.nextInt();
            rewards[i] = sc.nextInt();
        }

        // 输出最大奖励
        System.out.println(maxReward(T, n, times, rewards));
    }

    // 计算最大奖励的函数
    public static int maxReward(int T, int n, int[] times, int[] rewards) {
        // 初始化 DP 数组，dp[j] 表示时间限制为 j 时的最大奖励
        int[] dp = new int[T + 1];

        // 遍历每个任务
        for (int i = 0; i < n; i++) {
            int time = times[i];   // 当前任务的耗时
            int reward = rewards[i]; // 当前任务的奖励

            // 倒序遍历时间限制，确保每个任务只被选择一次
            for (int j = T; j >= time; j--) {
                // 更新时间限制 j 内的最大奖励
                dp[j] = Math.max(dp[j], dp[j - time] + reward);
            }
        }

        // 返回时间限制为 T 时的最大奖励
        return dp[T];
    }
}

C++解法

解题思路

更新中

C解法

解题思路

更新中

JS解法

解题思路

更新中

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

【华为OD-E卷-工作安排 100分（python、java、c++、js、c）】