这一讲介绍动态规划算法求解背包问题。下边介绍背包问题，一个旅行者随身携带

背包，放入背包的物品有n种，每种物品有2个参数，一个是重量，一个是价值，

背包最大的重量限制是b，每种物品可以放多个，

在不超过重量限制的条件下，怎么样选择放入背包的物品，使得背包的价值达到最大，

在这里我们不妨假设这些个重量、价值和背包总重都是正整数。

下面是一个具体的实例，一共有4种物品，背包的重量

限制是10，那么第一种物品的价值就是1，重量是2；第二种物品

价值3，重量3；第三种物品价值5，重量4；第四种物品价值9，重量7，

在这样的一个输入实例情况下，给出一个

背包的装法，使得它在不超过10的情况下，价值达到最大。

那么对这个问题建模，建模它的解可以表达成一个向量，

这里边xi是装入背包的第i种物品的个数，

那么对于背包问题，它的目标函数和约束条件是

下面这个公式来表示的。这里边对第i

种物品的个数乘以它的价值，然后对所有的物品来求和，当xi不为0的时候，它的价值

就被记录到背包里边去了，所以这一项是背包装入物品的

价值，那么下边一个是约束条件，就是说

你装入物品的重量呢应该用这个公式来计算。

计算的总重不超过b，而每个物品的个数是一个非负的整数，

我们希望这个价值目标是极大化，

下边是它的约束条件。对于这种问题，我们看到，可以看做它是一个

线性规划的问题，就是说它是约束条件和目标函数这两个

全部都是线性的一个函数，它是线性函数的

最大化，也是由线性函数来约束的。这个叫线性规划问题。

如果要求这些个x都是非负整数的时候，那么这个问题也可以叫作整数规划问题。

下面看一下背包问题的子问题怎么界定。

这个界定呢可以有两个参数来界定，k和y，k代表是物品的标号，

就是说我们现在只考虑第1，第2，一直到第k种，前k种物品，

那么这个k呢就界定了可以选择的物品个数。

这个y呢界定的是背包总重不超过y，

那么当k等于n，y等于b的时候，就是原始问题。也就是说，

所有问，子问题里边最大的那个子问题。那么在这个情况下，

我们可以看到子问题的计算顺序，我们可以先由第一个参数k 它分别是1，2，

一直到n这样的从小到大来变化，来界定这个子问题的大小。那么当给定了一个k以后，这个时候

我们让这个y也变化，y从1，2，一直到b变化，

所以先给出k，当k确定以后，然后y

再来从小到大地增长，这样就得到了一系列的子问题。

下边看一下它的优化函数，这个递推方程是什么。我们现在

假定是用一个优化函数Fk(y)，它表示是装前k种物品，

总重量不超过y的，在这个子问题中它的背包达到了最大价值。

那它的子问题的依赖关系的满足下面这个递推方程。

我们看一下这个方程。这个方程反应的是

在第k种物品装或者不装，两种选择，前面这一项Fk-1(y)，

那么在背包重量不超过y的时候，我只使用前k-1种物品来装。第k种

物品不用，后面这一项，就第k种物品要用，

那么它要用一个，产生的价值是vk，装入这个物品以后，背包占据了wk的重量，

剩下的重量是y-wk，那么这个重量由谁来填充呢？

还是由前k种物品来填充，这个地方下标是个k，

这反映什么呢？就是我继续还可以装入第k种物品，因此后边这一项

反映的是第k种物品可以装1个，装2个，甚至可以装更多的，这样的考虑。因此

我们就可以由这样的一个递推方程来得到它关于Fk(y)的这样的优化函数值，

那这样的方程的初值会比较多一些，一个是k等于0这个

初值是0，因为没有考虑任何的物品，那么当y等于0的时候，

重量限制是0，它也是等于0，不可能装入任何的物品，那么如果考虑只装第一种物品的时候，

y/w1下取整就是在这个时候能装入的最大的个数，

再乘以它的单位价值，这就是F1(y)的最优的值。那么这个地方有一个

当y<0的时候，Fk(y)是等于负无穷，因为我们发现这里有一个减，y-wk，

如果当时的y值比wk还小的话，这个括弧里边有可能是一个负数，那么负数实际上是

不存在这样的装法的，因为你装的重量已经要超重了，

这样就令它等于负无穷呢，在这两项选择的时候，就把这一项就抛弃掉了，

这就是为了处理这个边界情况。下面我们看一下

这样的递推方程，其实也可以考虑按照投资问题的办法来写出背包问题的递推方程。

按照投资问题的写法呢和现在的这种写法有什么区别呢？我们来看一下。

下边是按照投资问题那个方式来写的递推方程。这里边反映的是第

k种物品我们用xk个，那么它所产生的价值呢就是xk乘以vk，

当装了xk个第k种物品以后，它占据了xk乘以wk个

这样的重量，背包剩下的是y-xkwk

这一部分重量要由k-1种的物品来填充，它是这样的一个

考虑。所以这个xk表示装入的第k种物品的个数，

那这个个数呢可以有很多的选择，最少装入0，就是不装，装的最多的就是

y/wk下取整，就是它最可能多的那个个数。

把xk按照这样的范围里头所有可能的取值

都把它代入到这个公式里边算一下，然后比出其中的最大价值就可以了，这个

公式的写法就和投资问题的写法那个类似。那这两种写法有什么不一样呢？我们

分析一下。这个写法它的时间复杂度会低一些，为什么呢？我们看到这一项是可以

查的，因为前边根据子问题的计算顺序这项已经算过了，那么这一项其实也是可以查的，

尽管它底下的第一个下标都是k，但是y的这个值比这个子问题的y的值要小，所以

它也计算过了。这两项都不需要重新计算，因此我把这两个值查到，

这里做一次加法，再做一次比较就可以了。常数次计算就可以得到Fk(y)的值。

但是对于这个表达式，你要对错的xk都要遍历它所有可能的值，

那么当这个可能的值的取值要是比较大的时候，有可能跟这个y的

级别很接近，因此这一项的工作量不是由常数所能界定的。

它可能需要大概相当于O(b)这样的量级的工作量。所以这个方程的计算工作量

要小，这个方程的计算工作量要大。这是它们的区别。

下边我们看一下标记函数。因为背包你除了计算最大价值以外，还需要

考虑到底装的是哪些物品，那才是问题的解。这个标记函数反映的是

在考虑前k种物品，总重不超过y的时候，背包达到最大价值所装入物品的最大标号。

比如说我在这个时候装入的最大标号是4，那么这个值就是4

也就是说，当前装入物品的最大标号的物品就是4号物品，

那么它的计算也满足一个递推方程。

就看这两项，这项反映的是我要装第k种物品，

这项反映的是不装，就是只考虑前k-1种物品。如果不装的效果更好，

那就是说，我们现在装的最大标号至多跟前k-1种物品装的标号是一样的。所以等于i

k-1 (y) 如果是相反的情况，就是这一项的值更大，

也就是下面这个情况。当这个情况下，我就反映了装第k种物品的效果更好。

这个时候，我们就会装入k种物品。背包装入物品的标号呢就应该取k。

这是它的递推公式。通过这个递推公式，也可以从较小的前面的这些i

k-1 (y)等等来计算出ik（y）。

下边呢是它的初值。当只考虑第一种物品的时候，物品的重量都大于背包的重量限制，这个时候是不能装物品的。

如果当物品的

重量小于等于背包的限制，这时候至少可以把一号物品装进去。啊，这个是它的标记函数。

标记函数干什么用呢？是追踪解用的。我们看一个具体的计算实例，这就是刚才给的那个例子。

根据这个例子呢可以计算出它的所有的优化函数值，计算的顺序就是先算k=1，就是这第一行的，

第一行的，这个是y的增加，一直增加到10，所以我们计算顺序就是

从这个地方开始计算，啊，从这个地方开始计算。然后当对

k=1的情况计算完了，就计算k=2的情况，就是这一行的情况。

啊，当这一行计算完了，再计算第三行的，最后计算第四行的，

就根据刚才讲的那个递推方程来找到这些值就可以了。到这个表都计算完了以后，

最后这个位置的数12就是背包的最大价值，就是最优解

它达到最大价值就是12。那到底是怎么样装才能达到12的价值呢？

需要通过刚才的标记函数去追踪。下面我们看一下追踪过程。

这个是标记函数的表，i,k,y的表，啊，这个也是k=1的，

等于2的，这一行等于3的，这一行等于4的，啊，也是从这个地方开始追踪。

这个是i，4，10它的值等于4，那这项追踪说明什么呢？i4(10)要等于4的话，

说明在达到最大价值的时候，第4号物品被用过了，因为用到的标号是4。

那就意味着第4号物品至少用了一个，所以我们可以推出来X4的个数大于等于1。

然后，我们就看，当这个物品被用到以后，背包剩下的重量还有多少。背包原来重量是10，

第4号物品重量是7，一减掉以后还剩3。

那就是说我现在下面要考虑的是前4种物品

背包重量是3的时候用到的最大标号。要查i4(3)。i4(3)是谁呢？

4，3，i4(3)就是这一项。所以由这一项一下子就追踪到这样一项。

到这一项以后，这个值等于2，等于2说明在这个装法的条件下

装的物品的最大标号是2，那就意味着

第二种物品要至少装一个，第四种物品只装了一个，因为刚才装过一个，

现在再装的话最大标号只装到2了，所以第四种物品最终是装了一个，而第三种物品根本就

没有装。所以会推出这个结果。然后由这个我们再继续来考虑。

这个时候i4(3)是等于2，那么这时候第二种物品装了一个，第二个物品多重呢？正- 好是3，

3-3=0，i2(0)。这个时候背包的重量已经是0了，不可能再装任何物品了。啊，我们追踪就可以追到这个初值

就可以了。那么在这个情况下呢，我们可以发现X2

装了一个，因为刚才这是大于1的，而现在这个重量已经

限制到0了，不可能再装任何物品了，所以X2只装了一个，

而X1呢就不会再装了，因为这个是0，啊，所以就不能再装了。这是我们看到的它的追- 踪过程。

那么追踪最后的解是什么呢？就是把刚才这些个X的值都确认下来，第一个物品不装，

第二个物品装一个，第三个不装，第四个物品装一个，这个时候它的重量不超过10，

价值是12。这就把解追踪出来了。

那么追踪解的算法我们可以用一个伪码描述出来。

这个算法的输入就是我们的标记函数这个表，然后

追踪呢出来的就是X1、X2到Xn的取值，就是物品的装入数量。

那么我们看这个伪码，这个伪码里头它从一开始是赋初值的，

它从什么地方开始追踪呢？从这个最后一项的，

要是按照算法的话就是i,n,b，啊，从这个地方开始追踪。从

这个后边开始，啊，把它赋成这个第一个值。赋成第一个值以后呢，那这个就是

最后所装入的最大标号物品那个标号。那这个标号找到以后，对应的物品个数

先装一个，先赋成1，然后用重量减掉这个物品的重量以后，

啊，我们再看看还能不能继续装这个物品，就看看这个值是不是还是j。

因为现在j是最后一个，就是最大的标号了。

那么如果它继续等于j，意味着第j号物品还可以继续装，

我们就用它再减掉这个物品的重量，再看看把物品的个数增加一个，

再看看它是不是还能继续装。直到它不等于j了，那就是说，

得到一个比j小的值，那这个j号物品就不再装了，

会装它下一个物品。也就是说我们考察这个值是不是0，如果不等于0的话，

那么这个值就是下一种物品的标号，得到这个值以后就接着回到3，把这个标号赋到j，我们再继续追踪这个

j号物品装了多少个。啊，这就是刚才那个追踪的过程。

所以我们看到它基本上是两个部分，

第一个是初始的追踪位置，而这个地方呢就是继续放第j号物品的这个循环。

啊，那么到最后，这个地方就是要追踪下一种，啊，

它是从不满足条件，不等于0的话就继续追踪下一种，

这是它的三个主要的步骤。下面我们看一下时间复杂度的估计。

刚才我们已经提到了，这个公式的时间复杂度，

它是由这两项来决定的，而这个计算只需要常数时间。那么像这样的

fk(y)一共有多少个项呢？k的值可以有n种取值，y的值有b种取值，所以一共有n- b个项，

总的时间呢就是o(nb)就可以了，这是它的计算时间。那么这个算法，

它的时间看起来是一个n和b的多项式的时间，但是这个算法

并不是真正的多项式时间，因为这个时间并不是输入规模的多项式。

输入规模是什么决定的呢？我们这里面输入规模是两个参数，

一个是b，还有一个是n，那么作为b来讲它是一个整数，受背包重量的限制。

如果把一个整数存到计算机里面去，它用的位数是logb位，所以它的输入规模是

logb和n这两个参数。那么你要把这个函数来表示的时候，n和n

倒是多项式的关系，但是b不是logb的多项式函数。啊，所以我们把这样的算法，

表面看起来像是一个多项式，但是它不一定是真的多项式算法。我们把这样的算法叫做伪多项式时间的算法。

下面看一下背包问题的推广，刚才我们讲到的是一般的背包问题。

那么第一种推广就是物品数受限的背包问题。比如说我们限制第i种物品最多用ni个，

每个物品的个数都有一个限制，这样的是一种背包问题。这里面

最著名的是0-1背包，就是物品最多装一个，不装，或者装一个。啊，这是物品数

受限的背包问题。第二种呢是多背包的问题。现在有m个背包，

每个背包都有一个装入的最大重量的限制。

然后在满足所有背包重量约束的条件下，就是m个

约束都要满足，在这个条件下，使得装入物品的价值达到最大。啊，

这是多背包问题。还有呢，是二维的背包问题。我尽管是一个背包，

但是物品呢有两个约束，一个是重量有约束，还有一个体积的约束，

啊，体积的约束。那么在背包的重量不超过

b的情况下，而背包的体积不超过v，因为每个物品都有体积的大小，

我们装入背包的总体积不能超过v，重量不能超过b，有两个限制，二维的限制。在这个情况下

怎么选择物品使它得到最大的价值？啊，这个都是背包问题的

一种推广形式。下面我们把背包问题小结一下。

背包问题呢，它首先是子问题的界定，这里边界定有两个参数，

啊，一个是k，一个是y，啊，通过两个参数来界定。那么它的

优化函数的递推方程和边界条件也是由这样的两个参数来决定的这个递推方程。

边界条件呢，初值也是两个参数。

下面呢计算顺序，这两个参数不是同一种类型的，

不像矩阵链相乘，它是代表前后的位置都是相同类型的参数。那我们这不是同一类型的参数,

你要说明它的计算顺序，怎么样自底向上计算？哪个参数先

取各种值，然后当第一个参数固定以后，再来确定第二个参数的取值。

啊，然后根据这个子问题的计算顺序来设计备忘录，

来存储它的优化函数值和标记函数值。

设立标记函数到底怎么设立，它的追踪算法是什么？啊，这个要给出来。

最后，它的推广和应用，背包问题呢，它有

很多种不同的类型。啊，它的应用呢，在很多的实际问题

都可以与背包问题来建模。这是关于背包问题的介绍。

041背包问题

算法设计与分析 Design and Analysis of Algorithms

与讲师见面