考虑表6—1的实例,假设有3个物品,背包容量为22。图6—6中是根据上述算法构造的搜索树,其中结点的编

Question

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

对于表6—1的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为 (7) ，而用了上述回溯法，搜索树的结点数为 (8) .

Answer 1

正确答案：(5)2与3(6) 35(7) 15(8) 8
(5)2与3(6) 35(7) 15(8) 8 解析：本题实质上是一个0-1背包问题，该问题最优化的目标函数是
max∑vixi(xi=0，1)；
约束函数是：
∑pixi≤M(xi=0，1)。
0-1背包问题可用动态规划策略求得最优解，求解的递归式为
[*]
其中，nv[i][j]表示由前i项物品组合且价格不超过i的背包的总价值。问题最终要求的背包的总价值为nv[n][M]，根据上述递归式，可以很容易以自底向上的方式编写伪代码。
[问题1]中伪代码的第1行到第12行计算数组nv的元素值，第1行到第4行计算i为0或者j为0时nv[i]的值，对应递归式的第一种情况；第7行和第8行计算当j