Skip to main content

动态规划之背包问题

0-1 背包问题​

问题描述：一共有 NN 件物品，第 ii（ ii 从 11 开始）件物品的重量为 wiw_{i}，价值为 viv_{i}。每件物品只能装一次。在总重量不超过背包承载上限 WW 的情况下，能够装入背包的最大价值是多少？

dp[i][j]dp[i][j] 表示将前 ii 件物品装进剩余限重为 jj 的背包可以获得的最大价值，其中 0≤i≤N,0≤j≤W0 \leq i \leq N, 0 \leq j \leq W

那么我们可以将 dp[0][0...W]dp[0][0...W] 初始化为 00，表示将前 00 个物品（即没有物品）装入书包的最大价值为 00 。那么当 i>0i > 0 时 dp[i][j]dp[i][j] 有两种情况：

  • 不装入第 ii 件物品，即 dp[i][j]=dp[i−1][j]dp[i][j]=dp[i−1][j]；
  • 装入第 ii 件物品，但前提是能装下，也就是说剩余限重大于第 ii 件物品的重量，即 dp[i][j]=dp[i−1][j−wi]+vi,(j≥wi)dp[i][j]=dp[i−1][j−w_{i}] + v_{i} , (j \geq w_{i})。

那么可以得到转移方程

dp[i][j]={dp[i−1][j]=wi>Mmax={dp[i−1][j], dp[i−1][w−wi]}dp[i][j]=\left\{ \begin{aligned} dp[i-1][j] & = & w_{i}>M \\ max & = & \left \{ dp[i-1][j],\ dp[i-1][w-w_{i}] \right \} \end{aligned} \right.

完全背包问题​

完全背包（unbounded knapsack problem）与 0-1 背包不同就是每种物品可以有无限多个：一共有 NN 种物品，每种物品有无限多个，第 ii（ii 从 11 开始）种物品的重量为 wiw_{i}，价值为 viv_{i}。在总重量不超过背包承载上限 WW 的情况下，能够装入背包的最大价值是多少？

dp[i][v]=max{dp[i−1][v−k∗wi]+k∗pi ∣0≤k∗wi≤v}dp[i][v] = max\{dp[i-1][v-k*w_{i}]+k*p_{i}\ | 0 \leq k*w_{i} \leq v \}

其中 kk 为迭代量。

多重背包问题​

多重背包（bounded knapsack problem）与前面不同就是每种物品是有限个：一共有 NN 种物品，第 ii（ii 从 11 开始）种物品的数量为 nin_{i}，重量为 wiw_{i}，价值为 viv_{i}。在总重量不超过背包承载上限 WW 的情况下，能够装入背包的最大价值是多少？

dp[i][v]=max{dp[i−1][v], dp[i−1][v−j∗wi]+k∗pi ∣ 1≤k≤vwi}dp[i][v]=max\{ dp[i-1][v], \ dp[i-1][v-j*w_{i}] + k*p_{i} \ | \ 1 \leq k \leq \frac{v}{w_{i}} \}