工作安排-od-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
————————————————

# 输入处理
T, n = map(int, input().split())
jobs = [tuple(map(int, input().split())) for _ in range(n)]

dp = [0] * (T + 1)
for i in range(n):
    each_time = jobs[i][0]
    each_salary = jobs[i][1]
    for j in range(T, each_time - 1, -1): #反向遍历
        # 在这个问题中，dp[j]表示在耗时不超过j的情况下，可以获得的最大报酬。
        # 具体来说，dp[j]的含义是：在处理前i项工作时，耗时不超过j的情况下，可以获得的最大报酬。
        # 在动态规划中，dp[j]的更新过程考虑了两种情况：
        # 不选择第i项工作，所以dp[j]保持不变，即dp[j] = dp[j]。
        # 选择第i项工作，所以需要比较不选择第i项工作和选择第i项工作两种情况下的最大报酬：dp[j]和dp[j - each_time] + each_salary，
        # 其中each_time为第i项工作的耗时，each_salary为第i项工作的报酬。
        # 最终，dp[j]的更新值就是这两种情况中的最大值。整个动态规划的目标是找到在指定的工作时长内，可以获得的最大报酬。
        dp[j] = max(dp[j], dp[j - each_time] + each_salary)
print(dp[-1])