深圳网站建设工资杭州企业管理咨询有限公司

这两天把经典的三个背包问题看了一下，网上大多文章是以代码和公式为主，因为平时没刷过算法题所以理解起来花了些时间，固写一篇文章记录理解思路，本文不包含代码实现（理解了思路代码实现应该是小问题，网上一搜一大把，主要是思路！思路！思路！）

一、三个背包问题概述

因为三个背包问题实际上解决思路是几乎相同的，所以这里把三个问题放到一起进行记录，首先简单说下三个背包问题的题干

1.01背包问题：即有数件物品，每样物品均有不同的价值和重量，先给定一个背包容量大小，求背包能装下的最大价值。

2.完全背包问题：在01背包问题的基础上，每样物品有无限个（即可重复装包），求背包能装下的最大价值。

3.分组背包问题：在01背包问题的基础上，把数样物品改为数组物品，每组物品中只能选择一件，求背包能装下的最大价值。

二、动态规划及整体解题思路

个人理解动态规划简单来说就是对于当前状态，是某个过去状态的迭代结果，状态不断回溯存在一个初始固定状态并可以根据它推导出全部未来状态的一种模型，比如比较好理解的例如阶梯问题：漫画：什么是动态规划？ - 知乎———————————— 题目： 有一座高度是 10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。 比如，每次走1级台阶，一共走10步，这是其中一种走法。我们可…https://zhuanlan.zhihu.com/p/31628866

每一层台阶n层的走法数量是n-1层和n-2层决定的，即n层走法数等于n-1层的走法数加上n-2层的走法数之和，然后一直反推到第1（一种走法）层台阶和第2（两种走法）层台阶两个走法数确定的状态，即可推算出后续每一层台阶的走法数。

背包问题依然是使用这样的思路去解决问题，但对于背包问题来说比阶梯问题多了一个维度，是一个二维递归，理解起来相对来说会困难一点，在下文中会详细讲解图解思路，这里只对大概思路做一个说明：01背包中假设背包容量为10、物品中有一个物品容量占用为2价值任意的物品，那么对于该物品是否放入背包的问题取决于背包装到占用为8（即10-物品占用空间）时除该物品外其他全部物品装包方案的最大价值加上该物品的价值与除该物品外其他全部物品装满背包时的最大值做一个比较，价值总量最高的即为价值最大化方案，同样对于完全背包问题，只需要在01背包问题的基础上做一点点改动，对于10容量的状态只需要占用为8时全部物品装包方案的最大价值加上该物品的价值与除该物品外其他全部物品装满背包时的最大值做一个比较，价值总量最高的即为价值最大化方案，而分组背包问题只需要在01背包的基础上在把物品换乘组物品，并在每次比大小的时候循环对比组内全部物品大小即可，上述理解思路只是一个便于理解的大概思路，并不完全准确，因为物品是一件一件放入的，比较的过程也是动态的，接下来将对三个背包问题逐一图解，更加直观的解释解题思路。

三、01背包问题详解

 首先看上图，其中j轴表示背包容量大小，i轴表示物品，每一列都表示将每个物品依次尝试放入背包后状态的最大值，很显然我们可以得出如上图所示的这些初始状态格，当背包容量为10时我们需要的最大价值就是L6单元格的值，现在要做的就是根据上文中的比较方案进行逐一对比就能填充完全部单元格了，即对比占用为（j-物品占用空间）时除该物品外其他全部物品装包方案的最大价值加上该物品的价值与除该物品外其他全部物品装满背包时的最大值，由于我们的表格中放入物品是线性的，即有顺序的，因此比较中的除该物品外其他全部物品在每一步上时指根据i轴顺序该物品放入之前放入的其他全部物品（即i-1），这样只需要将数据推到第6行即是每个容量时的最大价值了，现在根据这个对比方式我们推一下E3单元格的值，此时j轴即背包容量为3，因此很容易知道我们仅仅需要去比较E2单元格的值和（B2单元格的值+4），取较大的即可，此时我们的表格变成了这样

 接下来发现存在E4这种单元格，它的（j-物品占用空间）超过了表格左象限，换句话说该j轴的情况下该物品还无法放入背包，因此在取最大值中直接取（i-1）的值即可，下面我们来根据规则将全部格子的值推导出来

即最大价值为19。

总结一下每个格子的状态公式，现在把每个物品的空间设为w，价值设为v，每个格子的值设为d，那么每个格子的公式（不考虑E4这种边界条件的情况下）为：d[i][j] = max(d[i-1][j], d[i-1][j-w[i]] + v[i])。

 四、完全背包问题详解

 我们依然以该模型为例，为了让过程更容易理解，我们把性价比最高的物品放到最下一行，其中初始状态值很明显有所不同，现在我们推一下E3单元格的值，此时j轴即背包容量为3，与01背包问题不同，因为完全背包问题中物品可以重复拿取，因此E3单元格需要比较的值变成了E2单元格的值和（B3单元格的值+4），根据这个思路我们直接推导出全部单元格数值如下

总结一下每个格子的状态公式，现在把每个物品的空间设为w，价值设为v，每个格子的值设为d，那么每个格子的公式（不考虑E4这种边界条件的情况下）则为：d[i][j] = max(d[i-1][j], d[i][j-w[i]] + v[i])，与01背包差别不大。

五、分组背包问题

分组背包问题思路与01背包基本相同，将i轴换乘物品组，每个格子进行最大值比较时循环将该组的每一个物品都套进01背包的公式中进行一次比较，从代码的角度无非是加了一层循环而已，因此不再进行详细图解及公式推导。