正确答案
1.斜线标识的部分完成的功能为:提前更新bestw值;
2.这样做可以尽早的进行对右子树的剪枝。具体为:算法Maxloading初始时将bestw设置为0,直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前,总有bestw=0,r>0 故Ew+r>bestw总是成立。也就是说,此时右子树测试不起作用。
3.为了使上述右子树测试尽早生效,应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加,因此,可以在算法每一次进入左子树时更新bestw的值。
试题解析