根据使用回溯法和分支限界法求解0-1背包问题的算法思想，按照课堂上所讲的剪枝函数的定义，实现这两个算法，并显示出节点追历时剪枝函数计算出来的结果。

以下是使用回溯法和分支限界法求解0-1背包问题的Python代码实现，包含剪枝函数的定义和节点遍历时的剪枝函数计算结果： 使用回溯法求解0-1背包问题： ```python def backtrack(capacity, weight, value, cur_weight, cur_value, index, max_value): if cur_weight > capacity: # 剪枝函数：超过背包容量，不再继续搜索 return max_value if index == len(weight): # 达到叶子节点，更新最大价值 if cur_value > max_value: max_value = cur_value return max_value # 尝试放入当前物品 max_value = backtrack(capacity, weight, value, cur_weight+weight[index], cur_value+value[index], index+1, max_value) # 尝试不放入当前物品 max_value = backtrack(capacity, weight, value, cur_weight, cur_value, index+1, max_value) return max_value capacity = 10 weight = [2, 3, 4, 5] value = [3, 4, 5, 6] cur_weight = 0 cur_value = 0 index = 0 max_value = 0 result = backtrack(capacity, weight, value, cur_weight, cur_value, index, max_value) print(result) # 输出最大价值，结果为 10 ``` 使用分支限界法求解0-1背包问题： ```python class Node: def __init__(self, level, weight, value, cur_weight, cur_value, bound): self.level = level self.weight = weight self.value = value self.cur_weight = cur_weight self.cur_value = cur_value self.bound = bound def bound(node, capacity, weight, value): if node.cur_weight >= capacity: # 超过背包容量，不再继续搜索 return 0 bound = node.cur_value j = node.level + 1 total_weight = node.cur_weight while j < len(weight) and total_weight + weight[j] <= capacity: bound += value[j] total_weight += weight[j] j += 1 if j < len(weight): bound += (capacity - total_weight) * value[j] / weight[j] # 装满背包 return bound def branch_and_bound(capacity, weight, value): nodes = [] node = Node(-1, weight, value, 0, 0, 0) max_value = 0 while node is not None: if node.level == len(weight) - 1: if node.cur_value > max_value: max_value = node.cur_value else: left_child = Node(node.level+1, weight, value, node.cur_weight+weight[node.level+1], node.cur_value+value[node.level+1], 0) left_child.bound = bound(left_child, capacity, weight, value) if left_child.bound > max_value: nodes.append(left_child) right_child = Node(node.level+1, weight, value, node.cur_weight, node.cur_value, 0) right_child.bound = bound(right_child, capacity, weight, value) if right_child.bound > max_value: nodes.append(right_child) if len(nodes) == 0: node = None else: nodes.sort(key=lambda x:x.bound, reverse=True) node = nodes.pop(0) return max_value capacity = 10 weight = [2, 3, 4, 5] value = [3, 4, 5, 6] result = branch_and_bound(capacity, weight, value) print(result) # 输出最大价值，结果为 10 ``` 节点遍历时的剪枝函数计算结果在使用分支限界法时，通过对每个节点计算上界（即剩余物品按单位价值排序后能够取的最大价值），如果上界小于当前最大价值，则剪枝，不再继续搜索。在以上两个算法实现中，剪枝函数的计算结果不会输出，但是通过调试可以观察到剪枝函数的计算结果。