摘要
Title: 2. 01背包问题
Tag: 01背包
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

2. 01背包问题

• 题意

  有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
  第 i 件物品的体积是 vi，价值是 wi。
  求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
  输出最大价值。

• 思路

  背包问题：组合问题求最优解

  01背包：每件物品只能用一次
  闫氏DP分析法，先写出朴素，再想优化
  

• 代码

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

  ---

  01背包补充版
  cnt 代表背包中物品数量
  num 代表背包中都有什么物品

  '''
  Author: NEFU AB-IN
  Date: 2022-03-07 22:55:35
  FilePath: \ACM\ACnowcoder\2020.3.7\j.py
  LastEditTime: 2022-03-07 23:01:21
  '''
  N = int(1e4 + 100)
  v, w, dp, cnt = [0] * N, [0] * N, [0] * N, [0] * N
  num = [[] for _ in range(N)]
  
  n, m = map(int, input().split())
  for i in range(1, n + 1):
      v[i], w[i] = map(int, input().split())
  for i in range(1, n + 1):
      for j in range(m, v[i] - 1, -1):
          if dp[j] < dp[j - v[i]] + w[i]:
              dp[j] = dp[j - v[i]] + w[i]
              cnt[j] = cnt[j - v[i]] + 1
              num[j] = num[j - v[i]] + [i]
  print(dp[m], cnt[m], num[m])