解题思路:
动态规划,背包问题
注意事项:
参考代码:
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])
0.0分
0 人评分