洛谷 P1060 [NOIP2006 普及组] 开心的金明

本文主要是介绍洛谷 P1060 [NOIP2006 普及组] 开心的金明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

[NOIP2006 普及组] 开心的金明 - 洛谷https://www.luogu.com.cn/problem/P1060

【分析】标准的01背包问题。

n, m = [int(i) for i in input().split()]
v, p = [0] * m, [0] * m
for i in range(m):v[i], p[i] = [int(j) for j in input().split()]
dp = []
for i in range(m + 1):dp.append([0] * (n + 1))
ans = 0
for i in range(m):for j in range(n):w = v[i]if j >= w:dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + w * p[i])else:dp[i + 1][j] = dp[i][j]ans = max(ans, dp[i + 1][j])
print(ans)

 

 

这篇关于洛谷 P1060 [NOIP2006 普及组] 开心的金明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---