当前位置：首页 > news >正文

最大报酬（E卷）

news 2024/11/5 11:56:27

题目描述：

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

输入描述

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

T 代表工作时长 (单位 h，0<T< 1000000)，

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][j]，表示前 i 个工作在 j 小时内能获得的最大报酬。

状态转移方程如下：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]] + w[i])  if j >= t[i]
dp[i][j] = dp[i-1][j]                               if j < t[i]

这个方程的含义是：对于第 i 个工作，有两种选择：做或不做。如果不做，那么最大报酬就是前 i-1 个工作在 j 小时内的最大报酬。如果做，那么需要先腾出这个工作所需的时间，然后加上这个工作的报酬。

dp[i-1][j] 表示不选择第 i 个任务时的最大报酬。
dp[i-1][j- job.t] + job.w 表示选择第 i 个任务时的最大报酬（前提是 j >= job.t 即给定的时间足以完成该任务）。

我们需要初始化 dp[0][j] = 0，因为在没有任务时，任何时间的报酬都是 0。

进阶

由于 dp[i][j] 仅依赖于上一行 dp[i-1][…]，我们可以将 dp 数组优化为一维，减少空间复杂度。

新状态转移方程为：

dp[j] = max(dp[j], dp[j-t[i]] + w[i])

注意，更新 dp 数组时，需要从后向前遍历，以确保在计算当前任务的状态时不会覆盖掉上一任务的状态。

源码 java

使用二维数组求解

// 使用二维数组求解
public class WorkReward2 {static Input input;static {input = new Input("40 3\n" +"20 10\n" +"20 20\n" +"20 5");}public static void main(String[] args) {String[] sts = input.nextLine().split(" ");int T = Integer.parseInt(sts[0]);int n = Integer.parseInt(sts[1]);// 做 i  份工作， 在 T 小时内可以获得的最大收益int[][] income = new int[n+1][T+1] ;for (int i = 1; i <= n; i++) {Job job = new Job(input.nextLine().split(" "));for (int j = 1; j <= T; j++) {if (j < job.t) {// 如果时间不足以完成该项工作，则此时的最大收益为 再吃 j 时间内完成 i - 1 件工作锁获取的收益income[i][j] = income[i - 1][j];} else {// 如果时间足够完成该项工作， 则最大收益为：做这个工作和不作这个工作之间 收益的最大值int doIt = income[i - 1][j - job.t] + job.w;int notDo = income[i - 1][j];income[i][j] = Math.max(doIt, notDo);}}}System.out.println(income[n][T]);}static class Job{public int t ;public int w;public Job(String[] s) {this.t = Integer.parseInt(s[0]);this.w = Integer.parseInt(s[1]);}}
}

使用一维数组求解

public class WorkReward {static Input input;static {input = new Input("40 3\n" +"20 10\n" +"20 20\n" +"20 5");}public static void main(String[] args) {String str = input.nextLine();int T = Integer.parseInt(str.split(" ")[0]);int n = Integer.parseInt(str.split(" ")[1]);int[] income = new int[T+1];for (int i = 0; i < n; i++) {Job job = new Job(input.nextLine().split(" "));for (int j = T; j >= job.t; j-- ){// 选择这份工作 总收益 = 干这份工作取得的收益  job.w + 减去这份工作需要时间后剩余的时间 可以获得的最大的收益 incone[j - job.t]// 不选择这份工作income[j] = Math.max(income[j], income[j - job.t] + job.w);}}System.out.println(income[T]);}static class Job{public int t ;public int w;public Job(String[] s) {this.t = Integer.parseInt(s[0]);this.w = Integer.parseInt(s[1]);}}
}