二叉树搜索求解背包问题

使用二叉树搜索（DFS、BFS和隐式搜索）求解背包问题

# -*- coding: utf-8 -*- # general binary-tree class BinaryTree: def __init__(self, value): self._value = value self._parent_node = None self._left_node = None self._right_node = None def get_right_branch(self): return self._right_node def get_left_branch(self): return self._left_node def get_parent_branch(self): return self._parent_node def set_right_branch(self, node): self._right_node = node def set_left_branch(self, node): self._left_node = node def set_parent_branch(self, node): self._parent_node = node def get_value(self): return self._value def set_value(self, value): self._value = value def __str__(self): return "Node Value: {}".format(self._value) # build Decision-Tree for knapsack problem def build_D_tree(sofar, todo): if len(todo) == 0: return BinaryTree(sofar) else: with_it = build_D_tree(sofar + [todo[0]], todo[1:]) without_it = build_D_tree(sofar, todo[1:]) # current node here = BinaryTree(sofar) # link left node <with it> here.set_left_branch(with_it) # link right node <without it> here.set_right_branch(without_it) return here # solve knapsack problem by searching Decison-Tree def DFS_D_tree(root, value_func, constrain_func): stack = [root] best = None visited = 0 while len(stack) > 0: visited += 1 if constrain_func(stack[0].get_value()): if best == None: best = stack[0] elif value_func(stack[0].get_value()) > value_func(best.get_value()): best = stack[0] temp = stack.pop(0) if temp.get_right_branch(): stack.insert(0, temp.get_right_branch()) if temp.get_left_branch(): stack.insert(0, temp.get_left_branch()) else: stack.pop(0) print("visited: {}".format(visited)) return best def BFS_D_tree(root, value_func, constrain_func): queue = [root] best = None visited = 0 while len(queue) > 0: visited += 1 if constrain_func(queue[0].get_value()): if best == None: best = queue[0] elif value_func(queue[0].get_value()) > value_func(best.get_value()): best = queue[0] temp = queue.pop(0) if temp.get_right_branch(): queue.append(temp.get_right_branch()) if temp.get_left_branch(): queue.append(temp.get_left_branch()) else: queue.pop(0) print("visited: {}".format(visited)) return best def DTree_implicit_search(to_consider, avail): if to_consider == [] or avail == 0: result = (0, ()) elif to_consider[0][1]> avail: result = DTree_implicit_search(to_consider[1:], avail) else: next_item = to_consider[0] with_val, with_to_take = DTree_implicit_search(to_consider[1:], avail - next_item[1]) with_val += next_item[0] without_val, without_to_take = DTree_implicit_search(to_consider[1:], avail) if with_val > without_val: result = (with_val, with_to_take + (next_item, )) else: result = (without_val, without_to_take) return result def sum_values(lst): vals = [e[0] for e in lst] return sum(vals) def weights_below10(lst): wts = [e[1] for e in lst] return sum(wts) <= 10 def main(): # the value of things and their weight a = [6, 3] b = [7, 2] c = [8, 4] d = [9, 5] e = [12, 4] # build D-Tree d_tree = build_D_tree([], [a, b, c, d, e]) print("-------- Using DFS -----------") # search by DFS foo = DFS_D_tree(d_tree, sum_values, weights_below10) # output things in the knapsack print(foo.get_value()) print("-------- Using BFS -----------") foo = BFS_D_tree(d_tree, sum_values, weights_below10) print(foo.get_value()) print("-------- Implicit search -----") foo = DTree_implicit_search([a, b, c, d, e], 10) print(foo) if __name__ == "__main__": main()

Note

更改weights_below10函数可以改变背包的重量限制