采药（python）（动态规划）

1.numpy

2.动态规划

import numpy
t, m = map(int, input().split(" "))
a = []
b = []
dp = numpy.zeros((m, t+1))
 
 
for i in range(m):
    c, d = map(int, input().split())
    a.append(c)
    b.append(d)
 
 
for i in range(m):
    for l in range(t+1):
            if a[i] > l:
                dp[i][l] = dp[i-1][l]
            else:
                dp[i][l] = max(dp[i-1][l], dp[i-1][l-a[i]]+b[i])
 
 
print(int(dp[m-1][t]))

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)