1100: 采药（背包问题）

核心：0-1背包问题，设置二维数组dp[i][j], dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi)
代码：

T, M = map(int, input().split())
l = [[0, 0]]
for i in range(M):
    l1 = [int(x) for x in input().split()]
    l.append(l1)
l.sort()
dp = [[0] * (T+1) for i in range(M+1)]  # 背包初始化
for i in range(1, M+1):  # 遍历物品
    for j in range(1, T+1):  # 遍历背包
        if l[i][0] > j:
            dp[i][j] = dp[i-1][j]
        else:
            wi = l[i][0]
            vi = l[i][1]
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] +vi)
print(dp[-1][-1])