动态规划解决方法——闫氏DP分析法

动态规划一般从两个角度来考虑问题，一个是状态表示，一个是状态计算。
状态表示指的是我们要思考要用几维来表示状态，背包问题一般是两维，即dp[i][j]。状态计算指的是我们如何能够一步一步地把我们的状态计算出来，即由之前的状态推导出现在的状态。

DP的优化一般是对DP问题的方程进行等价变形。所以我们首先思考朴素的做法，然后再优化。

闫氏DP分析法从集合的角度来思考问题，每一个状态表示一个集合。

对于状态表示，我们要思考dp[i][j]表示的是哪一个集合。虽然dp[i][j]是某一个集合，但它实际上存的是某一个数字，这个数字表示了集合的某种属性，属性一般有3种，最大值，最小值以及元素的数量，其中背包问题的属性是最大值。
状态计算对应的是集合的划分。具体而言，就是如何把当前的集合划分为若干个更小的子集，使得每一个子集都可以由前面的集合表示出来。背包问题对于dp[i][j]的分类是包含第i个物品以及不包含第i个物品。

划分依据：寻找最后一个不同点。
划分原则：不重不漏。

01背包问题

01背包概述：有N件物品和容量为V的背包，每件物品只能使用一次。第i件物品的体积是$v_i$，价值是$w_i$。求解将哪些物品放入背包中，在总体积不超过背包容量的情况下，物品的总价值最大。

分析：每一种物品都有选或者不选两种选择，那么实际的选法是$2^N$种。我们要做的就是在这么多种方案里选择价值最大的一种方案，因此该问题属于有限集合的最值问题。

根据闫氏DP分析法，我们用二维来表示状态，即dp[i][j]。它的含义是在前i个物品中选择，并且在总体积不超过j的情况下价值最大的集合。
依据划分原则，即最后一个不同点，我们可根据是否包含第i件物品划分集合。由于dp[i][j]的属性是最大值，因此dp方程可以写为：$dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i])$

具体过程见 https://www.acwing.com/blog/content/17442/ 。

完全背包问题

完全背包概述：有N种物品和容量为V的背包，每件物品可以使用无数次。第i件物品的体积是$v_i$，价值是$w_i$。求解将哪些物品放入背包中，在总体积不超过背包容量的情况下，物品的总价值最大。

分析：完全背包问题可以看作是01背包问题的延伸。具体而言，可以将若干件同种物品看作是若干件具有相同价值和体积的不同种物品。

当然，这只是方便我们理解。在解题的过程中，我们当然不能够因为我们理解而将第一个维度设置为无穷大，而是按照题意，将第一个维度设置为N，然后在体积的限制下，再加一重循环。详细来说，对于第i种物品，我们可以不选，也可以选。如果选，选多少件？(因为体积不是无穷大，因此虽然可以使用无数件同种物品，实际上可以使用的物品数量还是有限的)

因此，根据我们的分析，完全背包问题的dp方程式是：$dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i],dp[i-1][j - 2 \times v[i] ] + 2 \times w[i],\cdots,dp[i-1][j - k \times v[i] ] + k \times w[i])$。

考虑到有三重循环，我们可以对其进行优化。
注意到$dp[i][j - v[i]] = max(dp[i - 1][j - v[i]],dp[i-1][j - 2 \times v[i] ] + w[i],\cdots,dp[i-1][j - k \times v[i] ] + (k - 1) \times w[i])$。
给上面的式子两边同时加上$w[i]$,那么$dp[i][j] = max(dp[i - 1][j] ,dp[i][j - v[i]] + w[i])$
注意到完全背包问题dp方程和01背包问题dp方程的相似性，我们也可以对其空间进行优化。具体方法可参考01背包问题的降维优化。

多重背包问题

多重背包概述：有N种物品和容量为V的背包，第i种物品有$s_i$件，体积是$v_i$，价值是$w_i$。求解将哪些物品放入背包中，在总体积不超过背包容量的情况下，物品的总价值最大。

分析：由多重背包的概述可以看出，它实际上是“限定版”的完全背包问题，可以利用完全背包问题的解决方法求解；同时它也是01背包问题的延伸，当然可以利用01背包问题的解决方法求解。

如果使用完全背包问题的求解方法，只能利用完全背包问题最朴素的做法来做，即三重循环。
如果从01背包问题的角度来思考问题，不仅朴素做法使用，而且还可以对朴素做法进行二进制优化。下面我着重介绍多重背包的二进制优化方法。

多重背包的二进制优化
在朴素的做法中，我们把$s_i$件相同的物品看作是$s_i$件体积和价值相同的不同种类物品，这样就把多重背包问题转换为了01背包问题，即我们共有$\sum_{i=1}^{N}n_i\times s_i$件物品，每种物品只能使用1次。好了！现在我们已经知道多重背包问题实际上可以转换为01背包问题。现在让我们从完全背包问题的角度来思考问题。

在完全背包问题的朴素做法中，我们要对同一种物品再循环一次，判断我们需要多少件该类型的物品，这需要的时间复杂度较高。现在我们要想优化该朴素算法，就得想办法降低上述关键步骤的复杂度。因此优化的关键问题是如何以较低的时间复杂度来求解我们需要同种物品的数量。

我们可以将其进行“打包”，即将$n$个同种物品“打包”成一种新的物品，该新物品的价值是$n\times w_i$，体积是$n\times v_i$。“打包”的要求是“打包”后的物品组合可以表示从$0 \sim s_i$之间的所有物品。为此，我们想到了二进制优化方法，即$2^0 + 2^1 + 2^2 + \dots + 2^n + x = s_i$。将$s_i$分解为上式形式，每包的物品的数量是$2^i$或者$x$，而且它们的组合也可以将$0 \sim s_i$之间的数字全部表示出来。

因此问题的关键就在于$s_i$的二进制分解，如何将$s_i$分解为$2^0,2^1,\cdots,2^n,x$?进一步分析，如何确定$x$和指数$n$的值？已知$2^0 + 2^1 + \cdots + 2^n = 2^{n + 1} - 1$，那么$x = s_i + 1 - 2^{n+1}$。由于$x \geq 0$,所以$s_i - (2^{n+1} - 1) \geq 0$，这就是我们的循环条件。令$idx = 2^0$，每次循环s要减去idx，并且$idx$乘以2。循环结束时，就得到了“打包”后的物品。经过“打包”，同一种物品的价值和体积各不相同，且只能使用1次，因此可以当作01背包问题来求解。

分组背包问题

分组背包概述：有N组物品和容量为V的背包，第i组物品有$s_i$件，体积是$v_{ij}$，价值是$w_{ij}$,每组物品最多只能选择一个。求解将哪些物品放入背包中，在总体积不超过背包容量的情况下，物品的总价值最大。

分组背包问题的解决方法和完全背包问题类似，完全背包问题是第i组物品选几个，而分组背包问题是第i组物品选哪个？
可用完全背包问题的朴素做法求解。