背包问题是一类经典的动态规划问题，6月是leetcode的背包月，因此就最近做的几道背包题目，简单总结一下。

背包问题是一种组合优化的NP完全(NP-Complete,NPC)问题。问题描述：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择，才能使得物品的总价格最高。

背包问题一般有以下几种分类：

  • 01背包问题
  • 完全背包问题
  • 多重背包问题

01背包问题

题目

最基本的背包问题就是01背包问题(01 knapsack problem): 一共N件物品，第i(i从1开始)件物品的重量为w[i]，价值为v[i]，在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值多少？

分析

如果采用暴力穷举的方法，每件物品都存在装入和不装入两种情况，总的时间复杂度为O(2^N),使用动态规划可以将复杂度降至O(NW)

目标：书包物品的总价值

变量：物品和书包的限重

定义状态dp

dp[i][j]  // 表示将前i件物品装进限重为j的背包可以获得的最大价值，0 <= i <= N , 0 <= j <= W

初始化

dp[0][j] = 0 // i = 0时，dp[0][j]均为0

当i>0时，dp[i][j]有两种情况

  • 第i件物品不装入背包 ： dp[i][j] = dp[i-1][j]
  • 第i件物品装入背包 ： dp[i][j] = dp[i-1][j-w[i]] + v[i]

状态转移方程

// j >= w[i]
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])