最大报酬
题目描述：
小明每周上班都会拿到自己的工作清单，工作清单内包含 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]);
}
}
}
查看3道真题和解析