背包问题

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个重量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品只有1件。

  • dp[i][v] 表示前 i 件物品恰好装入容量为 v 的背包所能获得的最大价值
    • 不放第i件物品，则 dp[i][v] = dp[i-1][v]
    • 放第i件物品，那么问题转化为前 i–1 件物品恰好装入容量j – w[i]的背包中所能获得的最大价值 dp[i-1][v-w[i]] + c[i]
  • 递推方程dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]]+c[i]);