问答题
阅读下列说明，回答问题。
[说明]
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi，重量为wi(vi，和wi为非负数)，背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即
，且总重量不超过背包容量，即
，其中，Xi∈0，1，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。
[问题1]
用回溯法求解此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＜cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp, cw, k, W) ≤fp do
18 while k≠0 and Y(k) ≠1 do
19 (3)
20 if k=0 then return
21 Y[k]←0
22 cw←cw-w[k]
23 cp ← cp-v[k]
24 (4)
[问题2]
考虑表9.2的实例，假设有3个物品，背包容量为22。图9.1中是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择/不选择对应物品。除了根节点之外，每个左孩子节点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边的数字表示扩展了该节点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6) 。
[说明]
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi，重量为wi(vi，和wi为非负数)，背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即
，且总重量不超过背包容量，即，其中，Xi∈0，1，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。[问题1]
用回溯法求解此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＜cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp, cw, k, W) ≤fp do
18 while k≠0 and Y(k) ≠1 do
19 (3)
20 if k=0 then return
21 Y[k]←0
22 cw←cw-w[k]
23 cp ← cp-v[k]
24 (4)
[问题2]
考虑表9.2的实例，假设有3个物品，背包容量为22。图9.1中是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择/不选择对应物品。除了根节点之外，每个左孩子节点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边的数字表示扩展了该节点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6) 。
| 表9.2 0-1背包问题实例 | |||
| 物品1 | 物品2 | 物品3 | |
| 重量 | 15 | 10 | 10 |
| 价值 | 30 | 18 | 17 |
| 单位价值 | 2 | 1.8 | 1.7 |
【正确答案】[问题1] (1) k←1 (2) cw←cw+w[k] (3)k←k-1 (4)k←k+1
[问题2] (5)2和3 (6) 35 (7)8 (8)8
[问题2] (5)2和3 (6) 35 (7)8 (8)8
【答案解析】[要点解析] 该题考查用回溯法求解0-1背包问题。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择(走不通就退回再走这个过程就是回溯)。
本题的回溯法从所给的程序信息可以看出，分如下步骤。
①顺序将物品装入背包中(顺序搜索)，直到其物品总重量超过背包容量(即约束条件不满足)。
②如果直到物品全部放入背包中，背包总重量都未超过背包容量(约束条件满足)，则最优解得到。对fw(获得最大价值时背包的重量)、fp(背包获得的最大价值)、X(问题的最优解)赋予相应的值。
③否则，用界限函数BOUND判断扩展点(编号为k的物品)的上界，如果该值比当前获得的最大价值小了，则加入k物品对最优解无意义，进行剪枝。回溯。直到找到它的另一个分支结点。转①。
[问题1] 看代码可知，前3行是变量的初始化。当前的背包重量cw和当前获得的价值cp置0，当前考虑的物品编号k也需赋值，从l号物品开始。所以第(1)空填：K←1，第7行伪代码是对当前获得价值的更新，对照一下就可以得出第(2)空的[答案] cw←cw+w[k]。
BOUND函数用来计算上界，当这个上界小于等于背包获得的最大价值时，这个结点加入背包中无意义，回溯，因此第(3)空填写：k←k-1。第(4)空比较好理解，修改物品编号，继续搜索：k＜←k+1。
[问题2] 从图搜索树的结点可以看出，当选择根结点的右枝结点的时候，它的上界为35，比左枝结点大。所以，第(6)空为35。而其选择的是2和3号物品，所以，第(5)空为：2和3。
所谓穷举法是指枚举背包组合的所有可能，找出其最优解。有3个物品，为x、y、z，其中x、y、z都可以取0或1，则有2×2×2=8种组合。所以，第(7)空填：8。而第(8)空，由图9-1可知，为8个结点，故填：8。
本题的回溯法从所给的程序信息可以看出，分如下步骤。
①顺序将物品装入背包中(顺序搜索)，直到其物品总重量超过背包容量(即约束条件不满足)。
②如果直到物品全部放入背包中，背包总重量都未超过背包容量(约束条件满足)，则最优解得到。对fw(获得最大价值时背包的重量)、fp(背包获得的最大价值)、X(问题的最优解)赋予相应的值。
③否则，用界限函数BOUND判断扩展点(编号为k的物品)的上界，如果该值比当前获得的最大价值小了，则加入k物品对最优解无意义，进行剪枝。回溯。直到找到它的另一个分支结点。转①。
[问题1] 看代码可知，前3行是变量的初始化。当前的背包重量cw和当前获得的价值cp置0，当前考虑的物品编号k也需赋值，从l号物品开始。所以第(1)空填：K←1，第7行伪代码是对当前获得价值的更新，对照一下就可以得出第(2)空的[答案] cw←cw+w[k]。
BOUND函数用来计算上界，当这个上界小于等于背包获得的最大价值时，这个结点加入背包中无意义，回溯，因此第(3)空填写：k←k-1。第(4)空比较好理解，修改物品编号，继续搜索：k＜←k+1。
[问题2] 从图搜索树的结点可以看出，当选择根结点的右枝结点的时候，它的上界为35，比左枝结点大。所以，第(6)空为35。而其选择的是2和3号物品，所以，第(5)空为：2和3。
所谓穷举法是指枚举背包组合的所有可能，找出其最优解。有3个物品，为x、y、z，其中x、y、z都可以取0或1，则有2×2×2=8种组合。所以，第(7)空填：8。而第(8)空，由图9-1可知，为8个结点，故填：8。