编写题解 1103: 开心的金明

解题思路:

动态规划，背包问题

注意事项:

参考代码:

N, m = map(int, input().split())
sub_value = []
sub_importance = []

for _ in range(m):
   v, p = map(int, input().split())
   sub_value.append(v)
   sub_importance.append(p)

product = [[0] * (N + 1) for _ in range(m)]

for i in range(m):
   for j in range(N + 1):
       if sub_value[i] <= j:
           product[i][j] = max(product[i - 1][j], sub_importance[i] * sub_value[i] + product[i - 1][j - sub_value[i]])
       else:
           product[i][j] = product[i - 1][j]


print(product[m - 1][N])