完全背包

问题描述：

有N件物品和一个最多能背重量为V的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品都有无限个（也就是可以放入背包多次）。问如何选取物品放入背包，使得背包内的物品总价值最大？

决策方式：

（1）不放第i件物品

（2）放k件第i件物品，k>=1

状态转移方程：

\[ \begin{equation} dp[i][v] = \max\left\{ \max_{1 \leq k \leq \frac{v}{w[i]}} \left(dp[i-1][v-kw[i]] + kc[i]\right), dp[i-1][v] \right\} \end{equation} \]

其中dp[i][v]表示，容量为v时取前i个物品时背包能装入的最大值

化简

由于在第二种决策方式下，至少放一件 \[ \begin{equation} dp[i][v] = \max_{0 \leq k \leq \frac{v}{w[i]}-1} \left(\max\{dp[i-1][v-w[i]-kw[i]] + kc[i] + c[i], dp[i-1][v]\}\right) \end{equation} \] 对于状态转移方程可简化为： \[ \begin{equation} dp[i][v] = \max_{0 \leq k \leq \frac{v}{w[i]}} \left(dp[i-1][v-kw[i]] + kc[i]\right) \end{equation} \] 当v=v-w[i]时： \[ \begin{equation} dp[i][v-w[i]] = \max_{0 \leq k \leq \frac{v}{w[i]}-1} \left(dp[i-1][v-w[i]-kw[i]] + kc[i]\right) \end{equation} \] 整体替换到第二个公式中： \[ \begin{equation} dp[i][v] = \max\{dp[i][v-w[i]] + c[i], dp[i-1][v]\} \end{equation} \]

对比

01-背包状态转移方程： \[ \begin{align} dp[i][v] &= \begin{cases} \max\{dp[i-1][v-w[i]]+c[i], dp[i-1][v]\}, & \text{if } v - w[i] \geq 0 \\ dp[i-1][v], & \text{otherwise} \end{cases} \end{align} \] 完全背包状态转移方程： \[ \begin{equation} dp[i][v] = \begin{cases} \max\{dp[i][v-w[i]] + c[i], dp[i-1][v]\}, & \text{if } v - w[i] \geq 0 \\ dp[i-1][v], & \text{otherwise} \end{cases} \end{equation} \]

不难发现，完全背包状态转移方程仅仅比0-1背包状态转移方程少了一个-1

tips：0-1背包状态是回退到上一行，完全背包的状态仍然是当前行

一维滚动DP数组

图待更新

完全背包问题要沿着v的正方向进行枚举，这样才能为接下来的状态提供信息，否则当你需要计算dp[i][v]的时候，前面的dp[v-w[i]]还没有被更新过（同0-1背包问题完全一致，除了v的枚举方向）。

而0-1背包则需要逆向枚举v，防止要用到的上一行信息（dp[i-1][v-w[i]]）被覆盖为当前行（dp[i][v-w[i]]）