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

作者: 快乐的二叉树 | 来源:发表于2020-08-05 20:36 被阅读0次

01背包&无限背包问题&小鲁班的成长之路
背包九讲——Java详解
动态规划-背包问题
背包问题1（01背包）
完全背包--二维数组
背包问题2（完全背包）
最全 LeetCode 背包问题目录（持续更新）
01-背包、完全背包、多重背包及其相关应用
背包入门
算法-动态规划算法总结

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

一、基础问题

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$ 为止。

如图，共进行了四次查询，第一次查询发现没买，第四次查询无效，所以，最后买了两个3号装备。

相比之前，小鲁班的总收益提升了1点，但买这两件装备就花费了三分钟，这期间又送了两个人头。听着队友的无情嘲讽，小鲁班感到峡谷的风从未如此冷过。

参考文献

https://www.cnblogs.com/mfrank/p/10533701.html

01背包&无限背包问题&小鲁班的成长之路
利用有限的包容量，拿到最大价值的东西，在（每样只能拿一个，或者可以重复拿）的两种情况下，用动态规划的方法，求解，如...
背包九讲——Java详解
01背包问题每个物品只有选和不选两种状态完全背包问题每个物品可以无限次选多重背包问题 I 物品个数有数量限...
动态规划-背包问题
01背包问题详解：01背包问题详解链接
背包问题1（01背包）
N件物品，没见有重量Wi，价值Vi；选其中几件放入容量为M的背包中，求价值的最值。——经典背包问题背包问题分三类：...
完全背包--二维数组
完全背包问题是在01背包问题进行些改变，其大意为：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物...
背包问题2（完全背包）
01背包是指每件物品有且只有一件，而完全背包则是每件物品件数无限，求装入背包所对应的最值。完全背包也有公式，在01...
最全 LeetCode 背包问题目录（持续更新）
## 背包问题（目录） 1. 01背包 : [背包问题第一讲](https://mp.weixin.qq.com...
01-背包、完全背包、多重背包及其相关应用
本文介绍了背包问题系列，主要包括：【1】 01-背包及其应用【2】完全背包及其应用【3】多重背包【1】01-背...
背包入门
背包，是动态规划里一类典型的问题，主要有：01背包，完全背包，多重背包，混合背包，二维费用背包，分组背包，有依赖背...
算法-动态规划算法总结
1 基础问题 2 背包问题 2.1 01背包 2.2 完全背包 3 打劫问题 4 股票问题 5 子序列问题 5.1...

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

一、基础问题

1、问题描述

2、算法原理

3、求解过程

二、升级问题

1、问题描述

2、算法原理

3、求解过程

参考文献

相关文章

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

背包九讲——Java详解

动态规划-背包问题

背包问题1（01背包）

完全背包--二维数组

背包问题2（完全背包）

最全 LeetCode 背包问题目录（持续更新）

01-背包、完全背包、多重背包及其相关应用

背包入门

算法-动态规划算法总结

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读