I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course).I tried implementing dynamic programming first, and that worked fine, but ran into memory issues with larger datasets, so I decided to try branch-and-bound.My implementation works well for small datasets, but when I try and scale it, it hangs up like the DP algorithm, but I can't tell if it is because it is very slow or space inefficient.The way I have implemented it is as follows (in bad pseudocode)initialise global best value as 0initialise taken list and leave listinitialise priority queueinitialise root node with take and leave listsorder items by (value/weight)calculate upper bound of rootput root node in queuewhile queue not empty:    get queue element with highest priority (highest bound)    if current node bound < global best:        end because cant do better    if current node value > global best:        update global best    if current node level < item count        if weight with new item <= capacity            create new take list by copying current node take list and setting take[level] = 1            create new left node with new take list and old leave list        create new leave list by copying current node leave list and setting leave[level] = 1        create new right node with old take list and new leave list         The node class is:class node(level, take list, leave list):    set level as argument    set lists as argument    set value by iterating over take list and summing values    calculate room in bag by capacity - total weight calculated with take list    set bound by calculating using take and leave lists    left child = none    right child = noneMy question is: would it be more efficient to calculate the take and leave lists by traversing the tree rather than to explicitly store the lists in each node? I thought it might be quicker to store the lists and just update them with every new node, but I am thinking now that it might run into memory problems with large inputs.Is it not such a bad thing to have to traverse the tree every time I want to calculate the bound and should I worry more about space issues?
Making a branch-and-bound algorithm more efficient for a large input
algorithms;efficiency;knapsack problems;branch and bound