解题思路:01背包问题,利用动态规划思想,创建三个一维数组w[i],v[i],dp[i],分别用来存总价值=重要度*价格,价格,最大价值。
注意事项:
参考代码:
n,m=map(int,input().split())
w=[]
v=[]
dp=[0]*(n+1)
for i in range(m):
a,b=map(int,input().split())
w.append(a*b)
v.append(a)
for i in range(m):
for j in range(n,v[i]-1,-1):
dp[j]=max(dp[j],dp[j-v[i]]+w[i])
print(max(dp))
0.0分
2 人评分