title: How to implement a state-space tree?
body: <p>I'm trying to solve a knapsack like problem from <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-00Fall-2007/Assignments/index.htm" rel="nofollow noreferrer">MIT OCW</a>.
  Its problem set 5.</p>
  
  <p>I need use branch and bound algorithm to find the optimal states.
  So I need implement a state-space tree.
  I understand the idea of this algorithm, but I find it's not so easy to implement.</p>
  
  <p>If I find a node where the budget is not enough, I should stop here.
  Should I add an attribute to every tree node?</p>
  
  <p>When I add a node, I should start from a node with the largest upper bound.
  How can I find such a node? Do I need to traverse all the nodes before I add each node? Or could I save some var to help with that?</p>
  
  <p>Do you have any idea? Could you implement it in python?</p>