01背包&无限背包问题&小鲁班的成长之路

2020-08-05 本文已影响0人快乐的二叉树

利用有限的包容量，拿到最大价值的东西，在（每样只能拿一个，或者可以重复拿）的两种情况下，用动态规划的方法，求解，如何实现这个贪婪而有心计的想法。

一、基础问题

1、问题描述

假设小鲁班在开局一段时间后，存下了一笔金币，总量为 $X$ ，这时候他需要用这笔钱到商店里买装备，装备共 $Y$ 件，每件有对应的价格 $P_i$ 和收益值 $V_i$ ，先规定每种装备只能买一个，那么小鲁班该怎么买，才能让他总收益最大、在峡谷屹立不倒呢？

2、算法原理

问题核心在于，用有限的钱使装备总收益最大，求的是最大收益的买法。可以把这个问题分解为很多子问题，也就是归纳出一个统一的形式，即在装备数为 $i$ ，金币数为 $j$ 时能够得到的最大收益。直接看用动态规划怎么求解：
首先规定一个动态数组 $dp[i][j]$ ，表示在金币数为 $j$ 的时候，前 $i$ 件装备能带来的最大收益，有了这个设定，就可以从 $dp[0][0]$ 开始，依次填满动态数组，数组最后一个值 $dp[m][n]$ ，就是能达到的最大收益值。其中，每一次求 $dp[i][j]$ 的值，就是这个问题分解得到的子问题。

动态规划的递推公式如下：

$dp[i][j]=\begin{cases} dp[i-1][j],& {p_i>j}\\ max(dp[i-1][j],dp[i-1][j-p_i]+v_i),& {p_i<=j} \end{cases}$

当一件装备的价格 $p_i$ 大于了当前金币数 $j$ 时，说明买不了，现在的收益值只能等于前面装备能带来的收益值，也就是等于 $dp[i-1][j]$ ；
当一件装备的价格小于等于当前金币数时，说明可以买，但是买了它收益并不一定增大（因为当前的 $j$ ，并不是买完前面的装备后剩下的金币，而是这种情况下全部的金币，买了当前这个装备 $i$ ，有可能替换掉之前便宜又好用的某个装备，这样买完收益值反而变小了！）所以还需要做个对比，买它，收益值会变成 $dp[i-1][j-p_i]+v_i$ ，这里的 $dp[i-1][j-p_i]$ 就有可能放弃了某个便宜好用的装备，不买的话，收益值就还是 $dp[i-1][j]$ ，所以要取两种情况下的最大值。

3、求解过程

确定了递推方式，再来看一下dp数组的初始化，这里需要明确一下数值。假设小鲁班共有10个金币，装备种类有4个，它们的价格和收益值分别是： $P_i=\{5,3,5,2\},V_i=\{3,4,7,2\}$ ，其中 $i=1,2,3,4$ 代表装备序号。

所以，dp矩阵的维度就是 $dp[5][11]$ ，行和列都多了一个维度，是为了方便处理边界值。当 $i=0$ 或 $j=0$ 时，显然是没有实际意义的，但是后续的计算可能涉及回溯到 $i-1$ 的操作，为了避免错误，所以先把这两列都填充成0。

接下来，按照先 $i$ 后 $j$ 的方式，依次填表，也就是从左到右，从上到下。

可以看到，当 $i=1$ 时，只有一件装备，它的价格是5个金币，收益为3，这时候在 $j<5$ 时最大收益值都等于前面装备的最大收益，也就是 $dp[0][j]$ ；当 $j>=5$ 之后，最大收益就是第一件装备的收益值了。当 $i=2$ ，这时有两个装备可以选择， $j=8$ 时， $dp[2][8]=max(dp[2-1][8],dp[2-1][8-3]+4)=max(3,3+4)$ ，从表中可以看出，这时的结果为7，是同时选择了第一件和第二件装备得到的收益值。

最后把表填完，就得到了最后的最大收益值13，接下来需要知道，到底是买了哪几件装备，才能得到这个最大的收益？这时可以从 $dp[4][10]$ 往前查询，具体的步骤是：
判断 $dp[i][j]$ 是否等于 $dp[i-1][j]$ ，若两者相等，则说明没有买第 $i$ 件装备，从 $dp[i-1][j]$ 继续查询；若两者不相等，说明买了第 $i$ 件装备，再从 $dp[i-1][j-p_i]$ 查询。上述查询过程直到 $i=0$ 或者 $j=0$ 为止。

如图所示，共进行了四次查询，第四次 $j=0$ 无效，因此最后买的装备是2、3、4三件，小鲁班从此站了起来。

二、升级问题

1、问题描述

可是，现实总是不尽人意，鲁班小小的身体还是躺遍了峡谷每个角落。悲愤之余，躲在草丛里的鲁班，突然看到守约身上背了四把无尽，这一瞬间，小鲁班顿悟了。
峡谷商店里的东西不会限制购买次数，所以，一件高性价比的装备是可以重复买的！那么问题来了，在金币有限、并且一件装备能无限次购买的情况下，怎么买才能让小鲁班一雪前耻呢？

2、算法原理

同样的用动态规划的思路求解，规定一个动态数组 $dp[i][j]$ ，表示在金币数为 $j$ 的时候，前 $i$ 件装备能带来的最大收益，数组最后一个值 $dp[m][n]$ ，就是能达到的最大收益值。

只是需要改动一点，动态规划的递推公式如下：

$dp[i][j]=\begin{cases} max(dp[i-1][j],dp[i][j-1]),& {p_i>j}\\ max(dp[i-1][j],dp[i][j-1],dp[ i][j-p_i]+v_i),& {p_i<=j} \end{cases}$

当一件装备的价格 $p_i$ 大于了当前金币数 $j$ 时，说明买不了，但是现在的收益值需要对比一下两种情况，一是前面 $i-1$ 个装备能带来的收益值，也就是等于 $dp[i-1][j]$ ，二是用 $j-1$ 个金币在这些装备上的收益值，也就是 $dp[i][j-1]$ （因为现在第 $i$ 个装备有可能已经买过了，但是不影响，还可以买，所以需要考虑到这个情况），这两种情况下较大的那个收益，作为 $dp[i][j]$ 的值；
当一件装备的价格小于等于当前金币数时，说明可以买，同样地，买了它收益并不一定增大，所以也需要做个对比，不买的话，收益值就是 $p_i>j$ 时的收益，这时要取两种情况下的最大值；买它的话，收益值变成 $dp[i][j-p_i]+v_i$ ，这里之所以是 $i$ ，是因为不排除之前买过一次的情况，综合来看，需要取三个式子的最大值，作为 $dp[i][j]$ 的收益。

3、求解过程

同样的初始化方式，开始填表。

如上图所示，当计算 $dp[1][10]$ 时，刚好可以买两个第一件装备，所以值就等于 $dp[1][10-5]+3=6$ 。最后可以得到重复买的情况下，能达到的最大收益是14。
接下来查询买了哪几件，步骤是：
判断 $dp[i][j]$ 是否等于 $dp[i-1][j]$ 或 $dp[i][j-1]$ ，若有相等，则说明没有买第 $i$ 件装备，从相等的那个位置继续查询；若没有相等，说明买了第 $i$ 件装备，再从 $dp[i][j-p_i]$ 查询。上述查询过程直到 $i=0$ 或者 $j=0$ 为止。