华为OD机试 - 最大报酬 - 0/1 背包问题，动态规划（Java 2024 E卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

二、输入描述

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

T 代表工作时长（单位 h，0<T<1000000），n 代表工作数量（1<n≤3000）。

接下来是 n 行，每行包含两个整数 t, w。

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

三、输出描述

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

四、测试用例

1、输入

50 4
10 60
20 100
30 120
40 240

2、输出

300

3、说明

总工作时长 T = 50，有 4 个工作。

工作 1：耗时 10 小时，报酬 60
工作 2：耗时 20 小时，报酬 100
工作 3：耗时 30 小时，报酬 120
工作 4：耗时 40 小时，报酬 240

最佳选择是完成工作 1 和工作 4，总耗时为 10 + 40 = 50，总报酬为 60 + 240 = 300。虽然也可以选择其他工作组合，但报酬无法超过 300。

五、解题思路

基于经典的 0/1 背包问题，该问题可以用动态规划（Dynamic Programming, DP）来解决。

1、0/1 背包问题 & 动态规划

0/1 背包问题的本质是：给定一组物品，每个物品都有一个重量和一个价值，在限定总重量的情况下，选择一部分物品放入背包，使得这些物品的总价值最大。关键在于每个物品只能选择放或不放（即 0 或 1）。

动态规划是一种算法思想，它的本质是通过将问题分解为更小的子问题，并保存每个子问题的解，以此来避免重复计算并获得问题的最优解。

2、为什么采用 0/1 背包问题？

在题目中，我们要在一个固定的总工作时间内，选择一些工作完成，目的是最大化总报酬。这个问题与 0/1 背包问题非常相似：

背包的容量对应于总的可用工作时间。
每个物品的重量对应于每个工作的耗时时间。
每个物品的价值对应于每个工作的报酬。
选择物品放入背包对应于选择完成某个工作。

目标是选择一些工作，在不超过总时间的情况下，使得获得的报酬最大。

3、动态规划的应用

为了最大化总报酬，我们可以使用动态规划的思想：

定义状态：定义一个一维数组 dp[i]，表示在总时间不超过 i 的情况下，能够获得的最大报酬。
状态转移方程：
- 对于每一个工作 (t, w)（表示该工作需要时间 t，报酬为 w），我们可以选择是否完成它。
- 如果选择完成这个工作，那么总时间就减少 t，报酬增加 w，因此状态转移方程是：dp[i]=max(dp[i],dp[i−t]+w)
- 如果不选择这个工作，dp[i] 保持不变。
初始化：
- 初始化 dp[0] = 0，表示当时间为 0 时，报酬为 0。
最终结果：
- 最终，我们求得 dp[T]（T 是总的工作时长）即为最大报酬。

4、为什么从后往前更新

从后向前更新 dp 数组是为了确保每个工作只被计算一次。这样可以避免在同一轮次中多次使用同一个工作。

5、复杂度分析

时间复杂度：O(n * T)，其中 n 是工作数量，T 是总工作时长。

空间复杂度：O(T)，仅使用一维数组 dp。

六、Java算法源码

public class OdTest01 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入工作时长 T 和工作数量 nint T = sc.nextInt();int n = sc.nextInt();// 初始化动态规划数组 dpint[] dp = new int[T + 1];// 读取每个工作的耗时时间 t 和报酬 wfor (int i = 0; i < n; i++) {int t = sc.nextInt();int w = sc.nextInt();// 从后向前遍历，更新 dp 数组for (int j = T; j >= t; j--) {dp[j] = Math.max(dp[j], dp[j - t] + w);}}// 输出结果System.out.println(dp[T]);sc.close();}
}