01背包问题dp

解题思路:

注意事项:

参考代码:

a,b = map(int,input().split())
obj=[list(map(int,input().split()))for i in range(b)]
dp = list([0 for i in range(a+1)] for i in range(b))
for i in range(a):
    if obj[0][0]<=i:
        dp[0][i]=obj[0][1]
for i in range(1,b):
       for j in range(1,a+1):
           if j-obj[i][0] < 0:
               dp[i][j]=dp[i-1][j]
           else:
               dp[i][j] = max(dp[i-1][j], dp[i-1][j-obj[i][0]] + obj[i][1])
print(dp[-1][-1])