DP的背包问题小结-java语言描述

---

依然是复习以前学过的内容hhh

一、01背包

题目

一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

分状态和转移方程

显然变量为装入的物品和背包的质量，所求的目标是最大的价值。

因此设dp[i][j]来表示将前i件物品在j的限重下的价值最大值。

对于每个状态dp[i][j]有两种情况：

1. 装入第i件物品（dp[i-1][j-w[i]] + v[i]）

2. 不装入 （dp[i-1][j]）

故转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

二、完全背包

题目

同01背包类似，但每种物品可以取无限个。

分析

和01背包类似，我们设出同样的dp状态，dp[i][j]来表示将前i种物品在j的限重下的价值最大值。

还是分两种情况：

1. 装入第i种物品，但和01背包不一样，这里装入一次以后还可以继续装入，所以应该转移到dp[i][j-w[i]] + v[i]而不是dp[i-1][j-w[i]] + v[i]。

2. 不装入第i种物品（还是dp[i-1][j]）

所以转移方程为：

dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])

优化

这里可以做一个优化，可以通过滚动数组的方式，省去[i]，压缩空间复杂度。

转移方程可改写为：dp[j] = max(dp[j], dp[j-w[i]] + v[i])

这里注意时间复杂度是不能被压缩的，而且这样写的前提是循环时j必须正向枚举，确保此时访问的dp[j-[i]]已经在本次循环中被计算到。

01背包也可以类似优化，只不过要逆向枚举，确保此时访问的dp[j-[i]]是上一次循环计算到的结果。

三、多重背包

题目

和完全背包不一样在于每种物品的数量是指定好的。一共有N种物品，第i（i从1开始）种物品的数量为n[i]，重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

分析

因为指定了特定种类的物品数就相当于指定了n个独立的物品，所以多重背包问题可以直接化为01背包问题解决，其时间复杂度也不高。

转移方程可参考01背包。具体就是把给定数量的物品都视为单独的01背包里的物品来处理。

参考

动态规划之背包问题系列 - 知乎 (zhihu.com)