给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 W。一种物品要么全部装入背包，要么全部不装入背包，不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品，使得装入背包中的物品总价值最大?

01、问题分析——解空间及搜索条件

根据问题描述可知，0-1 背包问题要求找出 n 种物品集合{1,2,…,n}中的一部分物品，将这部分物品装入背包。装进去的物品总重量不超过背包的容量且价值之和最大，即找到 n 种物品集合{1,2,…,n}的一个子集，这个子集中的物品总重量不超过背包的容量，且总价值是集合{1,2,…,n}的所有不超过背包容量的子集中物品总价值最大的。

按照回溯法的算法框架，首先需要定义问题的解空间，然后确定解空间的组织结构，最后进行搜索。搜索前要解决两个关键问题，一是确定问题是否需要约束条件(用于判断是否有可能产生可行解)，如果需要，那么应如何设置？二是确定问题是否需要限界条件(用于判断是否有可能产生最优解)，如果需要，那么应如何设置？

1●定义问题的解空间

0-1 背包问题是要将物品装入背包，并且物品有且只有两种状态。第 i(i=1,2,…,n)种物品是装入背包能够达到目标要求，还是不装入背包能够达到目标要求呢？很显然，目前还不确定。因此，可以用变量 xi 表示第 i 种物品是否被装入背包的行为，如果用“0”表示不被装入背包，用“1”表示装入背包，则 xi 的取值为 0 或 1。该问题解的形式是一个 n 元组，且每个分量的取值为 0 或 1。由此可得，问题的解空间为：(x1,x2,…,xn)，其中 xi=0 或 1，(i=1,2,…,n)。

2●确定解空间的组织结构

问题的解空间描述了 2n 种可能的解，也可以说是 n 个元素组成的集合的所有子集个数。可见，问题的解空间树为子集树。采用一棵满二叉树将解空间有效地组织起来，解空间树的深度为问题的规模 n。图 1 所示描述了 n=4 时的解空间树。

图 1 n=4 时的解空间树

3●搜索解空间

(1) 是否需要约束条件？如果需要，那么应如何设置？

0-1 背包问题的解空间包含 2n 个可能的解，是不是每一个可能的解描述的装入背包的物品的总重量都不超过背包的容量呢？显然不是，这个问题存在某种或某些物品无法装入背包的情况。因此，需要设置约束条件来判断所有可能的解描述的装入背包的物品总重量是否超出背包的容量，如果超出，就为不可行解；否则，为可行解。搜索过程将不再搜索那些导致不可行解的节点及其节点。约束条件的形式化描述为

(2) 是否需要限界条件？如果需要，那么应如何设置？

0-1 背包问题的可行解可能不止一个，问题的目标是找一个所描述的装入背包的物品总价值最大的可行解，即最优解。因此，需要设置限界条件来加速找出该最优解的速度。

如何设置限界条件呢？根据解空间的组织结构可知，任何一个中间节点 z(中间状态)均表示从根节点到该中间节点的分支所代表的行为已经确定，从 z 到其子孙节点的分支的行为是不确定的。也就是说，如果 z 在解空间树中所处的层次是 t，从第 1 种物品到第 t-1 种物品的状态已经确定，接下来要确定第 t 种物品的状态。无论沿着 z 的哪一个分支进行扩展，第 t 种物品的状态就确定了。那么，从第 t+1 种物品到第 n 种物品的状态还不确定。这样，可以根据前 t 种物品的状态确定当前已装入背包的物品的总价值，用 cp 表示。第 t+1 种物品到第 n 种物品的总价值用 rp 表示，则 cp+rp 是所有从根出发的路径中经过中间节点 z 的可行解的价值上界。如果价值上界小于或等于当前搜索到的最优解描述的装入背包的物品总价值(用 bestp 表示，初始值为 0)，就说明从中间节点 z 继续向子孙节点搜索不可能得到一个比当前更优的可行解，没有继续搜索的必要；反之，则继续向 z 的子孙节点搜索。因此，限界条件可描述为

02、算法设计

从根节点开始，以深度优先的方式进行搜索。根节点首先成为活节点，也是当前的扩展节点。由于子集树中约定左分支上的值为“1”，因此沿着扩展节点的左分支扩展，则代表装入物品，此时，需要判断是否能够装入该物品，即判断约束条件成立与否，如果成立，就进入左孩子节点，左孩子节点成为活节点，并且是当前的扩展节点，继续向纵深节点扩展；如果不成立，就剪掉扩展节点的左分支，沿着其右分支扩展。右分支代表物品不装入背包，肯定有可能导致可行解。但是沿着右分支扩展有没有可能得到最优解呢？这一点需要由限界条件来判断。如果限界条件满足，说明有可能导致最优解，即进入右分支，右孩子节点成为活节点，并成为当前的扩展节点，继续向纵深节点扩展；如果不满足限界条件，则剪掉扩展节点的右分支，开始向最近的活节点回溯。搜索过程直到所有活节点变成死节点后结束。

算法伪码描述如下：

03、算法的改进

1●算法的改进思路

由 C［i］［j］的递归式(4-11)容易证明：在一般情况下，对每一个确定的 i(1≤i≤n)，函数 C［i］［j］是关于变量 j 的阶梯状单调不减函数(事实上，计算 C［i］［j］的递归式在变量 j 是连续变量，即为实数时仍成立)。跳跃点是这一类函数的描述特征。在一般情况下，函数 C［i］［j］由其全部跳跃点唯一确定，如图 2 所示。

图 2 阶梯状单调不减函数 C(i,j)及其跳跃点

利用该类函数由其跳跃点唯一确定的性质，来对 0-1 背包问题的算法 knapsack 进行改进，具体思路如下：

(1) 对每一个确定的 i(1≤i≤n)，用一个表 p［i］来存储函数 C［i］［j］的全部跳跃点。对每一个确定的实数 j，可以通过查找 p［i］来确定函数 C［i］［j］的值。p［i］中的全部跳跃点(j，C［i］［j］)按 j 升序排列。由于函数 C［i］［j］是关于 j 的阶梯状单调不减函数，故 p［i］中全部跳跃点的 C［i］［j］值也是递增排列的。

(2) p［i］可通过计算 p［i-1］得到。初始时令 p［0］={(0，0)}。由于函数 C［i］［j］是由函数 C［i-1］［j］与函数 C［i-1］［j-wi］+vi 做 max 运算得到的。因此，函数 C［i］［j］的全部跳跃点包含于函数 C［i-1］［j］的跳跃点集 p［i-1］与函数 C［i-1］［j-wi］+vi 的跳跃点集 q［i-1］的并集。容易得知，(s，t)∈q［i-1］当且仅当 wi≤s≤W 且(s-wi，t-vi)∈p［i-1］。因此，容易由 p［i-1］来确定跳跃点集 q［i-1］，公式为

(3) 另外，设(a，b)和(c，d)是 p［i-1］∪q［i-1］中的两个跳跃点，当 c≥a 且 d<b 时，(c，d)受控于(a，b)，从而(c，d)不是 p［i］中的跳跃点。也就是说，根据函数 c［i］［j］是关于 j 的阶梯状单调不减函数的特征，在跳跃点集 p［i-1］∪q［i-1］中，按 j 由小到大排序，如果出现 j 增加，c［i］［j］反而下降的点(j, c［i］［j］)，则不符合函数单调性，要舍弃。p［i-1］∪q［i-1］中的其他跳跃点均为 p［i］中的跳跃点。

(4) 由此可得，在递归地由 p［i-1］计算 p［i］时，可先由 p［i-1］计算出 q［i-1］，然后合并 p［i-1］和 q［i-1］，并清除其中的受控跳跃点得到 p［i］。

(5) 构造最优解。

第一步，初始时，i=n，j 初始化为 p［n］中的最大重量，m 初始化为 p［n］中的最优值。

第二步，检查 p［i-1］中的所有点(w，v)，如果 w+wi=j 并且 v+vi=m，则 xi=1，j=w，m=v，否则 xi=0。重复第二步，直到 i=0 为止。

按照算法的改进思路，具体的求解过程如下：

初始时，令 p［0］={(0，0)}。

在该并集中可以看到，跳跃点(2，3)受控于跳跃点(2，6)，因此将(2，3)从并集中清除，得到

在该并集中可以看到，跳跃点(6，5)受控于跳跃点(4，9)，因此将(6，5)从并集中清除，得到

由于跳跃点(13，15)和(15，18)已超出背包的容量 W=10，因此将它们清除，得到

在该并集中可以看到，跳跃点(5，4)受控于跳跃点(4，9)，因此将(5，4)从并集中清除，得到

同理，由于跳跃点(11，16)，(12，17)，(13，19)和(14，20)已超出背包的容量 W=10，因此将它们清除，得到

在该并集中的受控跳跃点有(4，6)、(7，10)、(8，11)、(9，13)和(10，14)，因此将它们从并集中清除，得到 p［5］={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}。

p［5］中最后的跳跃点(8，15)给出了装入背包的最优值 15 及装入背包的物品重量 8。

构造最优解过程：由于 p［4］中的(4，9)⊕(4，6)=(8，15)，故 x5=1，j=4，m=9；由于 p［3］中的所有点⊕(w4，v4)≠(j，m)，故 x4=0；p［2］中的所有点⊕(w3，v3)≠(j，m)，故 x3=0；p［1］中的(2，6)⊕(2，3)=(4，9)，故 x2=1，j=2，m=6；p［0］中的(0，0)⊕(2，6)=(2，6)，故 x1=1，j=0，m=0；求得的最优解为(1，1，0，0，1)。

04、Python 实战

1●0-1 背包问题的跳跃点算法

首先定义一个 merge_points()函数，完成跳跃点集合的归并排序。接收两个有序的点集，将其归并为一个有序的点集。其代码如下：

 其次，定义 knapsack_improve()函数，完成各子问题跳跃点的计算，从而求出原问题的跳跃点，得到问题的最优值。

定义 Traceback()函数，根据各子问题的跳跃点，逆向递推构造问题的最优解。其代码如下： 

 Python 程序入口——main()函数，在 main()函数中，给定 5 个物品的重量、价值和背包的容量，调用 knapsack_improve()函数得到最优值，再调用 Traceback()函数构造问题的最优解，最后将结果打印输出到显示器上。其代码如下：

输入结果为

最优解为：［1, 1, 0, 0, 1］