Powered by:NEFU AB-IN

Link

426. 开心的金明

• 题意

  见题面

• 思路

  01背包，只是价值变了

• 代码

  n, m = map(int, input().split())
  N = int(3e5 + 10)
  
  v, w, dp = [0] * N, [0] * N, [0] * N
  
  for i in range(1, m + 1):
      a, b = map(int, input().split())
      v[i] = a
      w[i] = b * a
  
  for i in range(1, m + 1):
      for j in range(n, v[i] - 1, -1):
          dp[j] = max(dp[j], dp[j - v[i]] + w[i])
  
  print(dp[n])