问答题 [说明]
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为v _i ，重量为w _i (v _i 和w _i 为非负数)，背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即 ，且总重量不超过背包容量，即

问答题 用回溯法求解此0-1背包问题，请填充下面伪代码中横线处的空缺。
回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根节点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前节点，若扩展该节点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的节点。现在假设已经设计了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 ______
3 fp ← -1
4 while true
5 while k≤n and cw+w[k]≤W do
6 ______
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 ← cw
14 k ← n
15 X ← Y
16 else Y(k) ← 0
17 while BOUND(cp, cw, k,Y)≤fp do
18 while k≠0 and Y(k)≠1 do
19 ______
20 if k=0 then return
21 Y[k] ← 0
22 cw ← cw - w[k]
23 cp ← op - v[k]
24 ______

问答题 考虑下表中所示的实例，假设有3个物品，背包容量为22。下图是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择/不选择对应物品。除了根节点之外，每个左孩子节点旁边的上、下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边数字表示扩展了该节点后最多可能获得的价值。为获得最优解，应该选择物品______，获得的价值为______。