一、题目描述
小明每周上班都会拿着自己的工作清单,工作清单内包含n项工作,每项工作都有对应的耗时时长(单位h)和报酬,工作的总报酬为所有已完成工作的报酬之和。那么请你帮小明安排一下工作,保证小明在指定的工作时间内完成工作收入最大化。
二、输入描述
输入的第一行为两个正整数T,n。
T代表工作时长(单位h,0 < T <100000),n代表工作数量(0 < n <= 3000)。
接下来是n行,每行包含两个整数t,w。
t代表该项工作消耗的时长(单位h,t > 0),w代表该项工作的报酬。
三、输出描述
输出小明指定工作时长内可获得的最大报酬。
四、解题思路
- 读取输入的工作时长 T 和工作数量 n;
- 创建两个数组 timeArr 和 workArr,用于存储每项工作的时长和报酬;
- 读取每项工作的时长和报酬,并将其存入对应的数组中;
- 创建一个二维数组 dp,其中 dp[i][j] 表示在前 i 项工作中,使用时长不超过 j 的情况下的最大报酬;
- 初始化 dp 数组的第一行和第一列为0,表示不选择任何工作或不使用任何时长时的最大报酬为0;
- 使用动态规划的思想,遍历所有工作和时长的组合,更新 dp 数组;如果第 i 项工作的时长小于等于当前时长 j,则可以选择该工作,更新 dp[i][j] 为