问答题
试题四（共15 分）
阅读下列说明，回答问题1 至问题2，将解答填入答题纸的对应栏内。
【说明】
0-1 背包问题可以描述为：有n 个物品，对i=1,2,···,n，第i 个物品价值为vi,重量为wi(vi 和wi 为非负数），背包容量为W(W 为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即
,且总重量不超过背包容量，即
,且总重量不超过背包容量，即
问答题
【问题1】（8 分）
用回溯法求解此0-1 背包问题，请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法，在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往假设已经设计了界函数，判断并剪枝那些即扩展了也不能得到最优解的结点。现在假设已经设计了BOUND（v,w,k,W）函数，其中v,w,k 和W 分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得最大的价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。
下面给出0-1 背包问题的回溯法伪代码。
函数参数说明如下：
W：背包容量；n:物品个数；w:重量数组；v:价值数组；fw:获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。
变量说明如下：
cw:当前的背包重量；cp:当前获得的价值;k:当前考虑的物品编号；Y:当前已获得的部分解。
BKNAP（W,n,w,v,fw,fp,X）
1 cw←cp←0
2 (1)
3 fp←-1
4 while true
5 while k≤n and cw+w[k] ≤W do
6 (2)
7 cp←cp+v[k]
8 Y[k] ←1
9 k←k+1
10 if k>n then
11 if fp
【正确答案】（1）k←0,或其等价形式
（2）cw←cw+w[k] , 或其等价形式
（3）k←k-1, 或其等价形式
（4）k←k+1, 或其等价形式
【答案解析】本题考查的是用回溯法求解0-1背包问题。回溯法有两类算法框架：非递归形式和递归形式，本题采用非递归形式表示。理解回溯法的基本思想和这两类算法框架是正确解答本题的根本要求。
回溯法从第一项物品开始考虑是否应该装入背包中，因此当前考虑的物品编号k从 1开始，即k←1。然后逐项往后检查，若能全部放入背包则将该项放入背包，此时背包的重量应该是当前的重量加上当前考虑物品的重量，即cw←cw+w[k]，当然背包中物品的价值也为当前的价值加上当前考虑物品的价值。若已经考虑完了所有的物品，则得到一个解，判断该解是否为当前最优，若为最优，则将该解的信息放入变量fp、fw和X中。若还没有考虑完所有的物品，意味着有些物品不能放入背包，此时先判断若不将当前的物品放入背包中，则其余物品放入背包是否可能得到比当前最优解更优的解，若得不到则回溯；否则继续考虑其余的物品。
问答题
【问题2】（7 分）
考虑表4-1 的实例，假设有3 个物品，背包容量为22。图4-1 中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字1/0 分别表示选择/不选择对应物品，除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择特(5),获得的价值为(6).
表4-1 0-1 背包问题实例
【正确答案】（5）物品2 和物品3
（6）35
（7）15
（8）8
【答案解析】根据问题1中给出的伪代码运行该实例，可以很容易得到此0-1背包问题的最优解，应该选择物品2和物品3，此时背包的重量为10+10=20，获得的价值为17+18=35。
若采用穷举法搜索整个解空间，即要构造一颗完全二叉树，此时搜索树的结点数应为24-1=15，而采用了上述回溯法，搜索树的结点数仅为8个，如上图所示。
本题考查算法设计技术——回溯法。
此类题目要求考生掌握基本的算法设计技术，包括分治法、动态规划法、贪心算法、回溯法和分支限界法等，然后结合具体的问题，用对应的算法设计技术来解决问题。