C＋算法主题系列之集结0-1背包问题的所有求解方案

1. 前言

背包问题是类型问题，通过对这一类型问题的理解和掌握，从而可以归纳出求解此类问题的思路和模板。

背包问题的分类有：

背包问题，也称为不可分割背包问题。

无限背包问题。

判定性背包问题.

带附属关系的背包问题。

双背包求最优值.

构造三角形问题.

带上下界限制的背包问题()

……

本文将介绍背包问题的各种求解方案，通过对各种求解方案的研究，从而全方面了解背包问题的本质。

2. 背包问题

问题描述：

有一背包，能容纳的重量为 ，现有 种物品，每种物品有重量和价值 个属性。请设计一个算法，在不分割物品的情况下，保证背包中所容纳的物品的总价值是最大的。

背包也称为完全背包或不可分割背包问题，是一类常见的背包问题。常用的实现方案有和 。

2.1 递归算法

可以有 种写法。

2.1.1 第一种递归回溯方案

回顾递归回溯算法适合的问题域：

待解决的问题可以分多步。如迷宫问题、排列组合问题……

每一步都可能存在多个选择，当某一个选择行不通，或此选择结束后，可以回溯到上一步再另行选择。

那么背包问题是否适合上述的要求？

可以想象背包里有很多个格间。当每一个格间填充完毕，则表示得到一种求解。

对于格间而言，每一种物品都是一种选择，可以通地回溯再选择另一个物品。

其本质是对物品进行任意组合，然后再选择总价值最大的一种组合。

如下图，有 个物品需要放置入容量为 的背包中。初始可把背包想象成一个大格间，此时可以试着放入物品中的一个。

物品放入格间的条件：

物品不曾在背包中。

物品的重量小于或等于背包现有容量。

如下图，把放入背包中。且把背包剩下空间想象为一个格间，在余下的物品中选择一个放入此格间中。

如下，把放入格间中。

因和的重量之和为 。等于背包总容量。此时，背包中已经没有剩余空间。也意味着不能再向此背包中放入物品。

至此，可以输出背包中的物品，且把背包中的总价值 存储在全局变量中，以便在后续操作时，查找是否还有比此值更大的值。

回溯物品

所谓回溯物品，指把物品从背包中移走，试着再放入一个其它物品。

如下图，回溯，腾出格间。因满足放入条件，放入格间。

此时，背包还有剩余空间，同样把剩余空间想象成一个格间。因有剩余空间，可以试着把放入背包中。

但因物品二的重量大于背包已有的容量，不能放入。此时，可以输出背包中的物品信息，并记录背包中的最大价值为。因比前面的的值小，继续保留 这个价值为当前最大值。

对上述流程做一个简单总结：

当背包还有空间，且有物品可以放入时，则加入到背包中。

当背包不再能放下任何一件物品时，计算此时的总价值，并确定是不是最大价值。

Tips：这里有一点需要注意，递归函数的出口有 个，一是还有物品可选择，但不能放入背包中。二是不再有物品可供选择。

回溯当前已经放入物品，选择其它物品，重复上述过程，一直到找到真正的最大值。

代码如下所示：

测试结果：

2.1.2 第二种回溯方案

第一种回溯方案，略显复杂，可以采用下面的回溯方案。

此方案中把物品可放入和不可放入做为选择。但其本质和上述实现是一样的。

2.1.3 第二种方案

前两种方案，不仅可得到最优值，且可以得到寻找过程中的各种组合方案。如果仅仅是想得到最终结果，不在乎中间的过程，则可以使用下面的递归方案。

2.2 动态规划

背包问题，有 个状态值，背包的容量和可选择的物品。

物品对于背包而言，只有 种选择，要么装下物品，要么装不下，如下图所示，表格的行号表示物品编号，列号表示背包的重量。单元格中的数字表示背包中最大价值。当物品只有一件时，当物品重量大于背包容量，不能装下，反之，能装下。如下图，物品重量为 。无论何种规格容量的背包都能装下（假设背包的容量至少为 ）。

如下图，当增加重量为 的物品后，当背包的容量为 时，不能装下物品，则最大值为同容量背包中已经有的最大值。

但对容量为 的背包而言，恰好可以放入新物品，此时背包中的最大价值就会有 个选择，一是把物品 放进去，背包中的价值为 。二是保留背包已有的价值。然后，在两者中选择最大值 。

当背包容量是 时，物品也是可以放进去的。此时背包的价值可以是当前物品的价值 加上背包剩余容量能存放的最大价值，计算后值为 。要把此值和不把物品放进去时原来的价值 之间进行最大值选择。

所以，对于背包问题，核心思想就是：

如果物品能放进背包：则先计算出物品的价值加上剩余容量能存储的最大价值之和，再找到不把物品放进背包时背包中原有价值。最后在两者之间进行最大值选择。

当物品不能放进背包：显然，保留背包中原来的最大价值信息。

2.3.3 编码实现

输出结果：

3. 总结

本文主要讲解背包系列 中的背包问题。背包问题可以使用递归和动态规划方案得到其解。