Added a few embellishments to the code for clarity to include title and number of items in the pack as well as ordering from top to bottom.
Everything is easier with the python as your friend. I assumed correctly that an interface to "GraphViz" dot language had been implemented in python. So here is the tree solution from the previous post ( generally) and it indicates the maximum or last maximum knapsack in gray. It incorporates trees, knapsack, directed graphing, python and even recursive programming. So this actually solves the knapsack in general. Just an exercise in programming.
import pydot graph = pydot.Dot(graph_type='digraph') home_dir="/home/user/" values = [9,7,8] weights = [5,3,2] item_names = ["vase","coin","ring"] best_color="gray68" best_style="filled" best_shape="box" knapsack_holds = 5 tree_depth = len(values) pack_best = 0 node_best = pydot.Node("No win", style=best_style, fillcolor="red") def create_node(source_node,dest_node): edge = pydot.Edge(source_node,dest_node) graph.add_edge(edge) def create_best_node(dest_node): return pydot.Node(dest_node, style=best_style, fillcolor=best_color, shape=best_shape ) def create_node_name(level,pack_free,pack_value): global pack_best global node_best node_a = create_best_node("Level %d Weight %d Value %d" % ( level, knapsack_holds-pack_free, pack_value )) if pack_value>=pack_best: node_best=node_a pack_best=pack_value return "Level %d Weight %d Value %d" % ( level, knapsack_holds-pack_free, pack_value ) def make_node(level,pack_free,pack_value): source_node=create_node_name(level, pack_free, pack_value) if pack_free-weights[level] >= 0: dest_node=create_node_name(level-1, pack_free-weights[level], values[level]+pack_value ) create_node(source_node,dest_node) if level > 0: make_node(level-1,pack_free-weights[level],values[level]+pack_value) dest_node=create_node_name( level-1, pack_free, pack_value ) create_node(source_node,dest_node) if level > 0: make_node(level-1,pack_free,pack_value) if __name__ == "__main__": make_node(tree_depth-1,knapsack_holds,0) graph.add_node(node_best) graph.write_png(home_dir+"knapsack_tree.png")
0 comments:
Post a Comment