华为OD笔试题：工作安排 --- 100分 （思路+python代码）

题目：

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

输入描述：
输入的第一行为两个正整数T，n。T代表工作时长（单位h，0 < T < 100000），n代表工作数量(1 < n ≤ 3000)。
接下来是n行，每行包含两个整数t，w。t代表该项工作消耗的时长（单位h，t > 0），w代表该项工作的报酬。

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

示例：
输入：
40  3
20  10
20  20
20  5
输出：
30

考查知识点：
动态规划 ------ 01背包（笔试常考点，题库有多道相似题目，一定要加深理解）

思路分析：
本题可以通过二维dp和一维dp两种方法解答。
对于每一项工作应该比较：做该工作(减去该项工作付出的时间，并加上该工作相应报酬)和不做该工作，保留这两种情况收益大的结果。
一维数组优化一定要注意必须从后向前覆盖，来正确计算前面的状态。
建立dp数组要注意(t+1)*(n+1)，且遍历时也要从1开始遍历，防止0-1出界。
动态规划问题建议根据代码手动填写一遍dp数组，文字解释往往对理解帮助不大。
背包问题有固定模板，多练习即可掌握。

python代码：（两种解法）
笔试时变量请自行处理

# t:工作总时长，n:工作数量， time：工作时间数组，earnings：工作报酬数组

#解法1：二维dp
def solve1(t, n, time, earnings):  
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(time[i - 1], t + 1):
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i - 1]] + earnings[i - 1])
    return dp[-1][-1]


#解法2：一维dp优化解法
def solve2(t, n, time, earnings):
    dp = [0 for _ in range(t + 1)]
    for i in range(1, n + 1):
        for j in range(t, time[i - 1] - 1, -1):
            dp[j] = max(dp[j], dp[j - time[i - 1]] + earnings[i - 1])
    return dp[-1]


if __name__ == '__main__':
    t = 40
    n = 3
    time = [20, 20, 20]
    earnings = [10, 20, 5]
    res1 = solve1(t, n, time, earnings)
    res2 = solve2(t, n, time, earnings)
    print(res1 == 30)
    print(res2 == 30)