My Question/Goal of the Review: To provide some context, the code I've written is included below. Please let me know if you have improvements on its structure (for example, is it better practice to make TreeNode a truly recursive object and give it left and right attributes? Do we gain anything by doing this?). What I'm really looking for, though, is how we can improve the current depth first search implementation (please don't provide a solution that uses a heap, for example, unless you can demonstrate it is an all around better algorithm than what I've written). If you'd like to provide code, that would be great, but I'm really just looking for some ideas on how my current code might be optimized. I'm kind of new to optimization and don't really know where to look for improvements or really how to think about the problem as might a person with a speciality in optimization.

One other question: while searching, if we include an item, do we need to recalculate the bound on this node (or would it just be the value of its parent--this solution is still attainable)?

Edit

My question/goal of the review:

To provide some context, the code I've written is included below. Please let me know if you have improvements on its structure (for example, is it better practice to make TreeNode a truly recursive object and give it left and right attributes? Do we gain anything by doing this?). What I'm really looking for, though, is how we can improve the current depth first search implementation (please don't provide a solution that uses a heap, for example, unless you can demonstrate it is an all around better algorithm than what I've written). If you'd like to provide code, that would be great, but I'm really just looking for some ideas on how my current code might be optimized. I'm kind of new to optimization and don't really know where to look for improvements or really how to think about the problem as might a person with a speciality in optimization.

While searching, if we include an item, do we need to recalculate the bound on this node (or would it just be the value of its parent--this solution is still attainable)?

class TreeNode:

    def __init__(self, level, V, W, taken):

        self.level = level
        self.V = V
        self.W = W
        self.taken = taken
    
    def __str__(self):
        return str((self.level, self.V, self.W, self.taken))


class KP:

    def __init__(self, cap, values, weights):
    
        self.capacity = cap
        self.values   = values
        self.weights  = weights

        self.ordered = sorted([((v, w), i) for i, (v, w) in enumerate(zip(self.values, self.weights))],
                          key = lambda tup: float(tup[0][0])/tup[0][1], reverse = True)

    def _greedy_solution(self):
    
        weight = 0
        value  = 0
        taken  = []

        for (v, w), index in self.ordered:
        
            if w + weight <= self.capacity:
                value  += v
                weight += w
                taken.append(index)
            
            else:
                return TreeNode(index, value, weight, taken)
        
        return TreeNode(index, value, weight, taken)


    def solve(self):
    
        best = self._greedy_solution()
        root = TreeNode(0, 0, 0, [])

        stack = [root]

        while len(stack) > 0:

            current = stack.pop()
            index   = current.level

            if current.V >= best.V:
                best = current

            if index < len(self.values):


                if current.W + self.weights[index] <= self.capacity:
                    taken = list(current.taken)
                    taken.append(index)

                    right = TreeNode( index + 1, current.V + self.values[index],
                                  current.W + self.weights[index], taken )

                    if right.V > best.V:
                        best = right
                
                    bound = self._linear_relaxation(index, right.V, right.W)

                    if bound >= best.V:
                        stack.append(right)

                left  = TreeNode( index + 1, current.V, current.W, list(current.taken) )
                bound = self._linear_relaxation(index, left.V, left.W)

                if bound >= best.V:
                    stack.append(left)

               
        return best 

class TreeNode:

    def __init__(self, level, V, W, taken):

        self.level = level
        self.V = V
        self.W = W
        self.taken = taken
    
    def __str__(self):
        return str((self.level, self.V, self.W, self.taken))


class KP:

    def __init__(self, cap, values, weights):
    
        self.capacity = cap
        self.values   = values
        self.weights  = weights
        
        # sort the items according to their value per weight 
        self.ordered = sorted([((v, w), i) for i, (v, w) in enumerate(zip(self.values, self.weights))],
                          key = lambda tup: float(tup[0][0])/tup[0][1], reverse = True)

    # our best initial solution will be the greedy solution 
    def _greedy_solution(self):
    
        weight = 0
        value  = 0
        taken  = []

        for (v, w), index in self.ordered:
        
            if w + weight <= self.capacity:   # take items of highest value per unit weight, while we still can
                value  += v
                weight += w
                taken.append(index)
            
            else:
                return TreeNode(index, value, weight, taken)
        
        return TreeNode(index, value, weight, taken)


    def solve(self):
    
        best = self._greedy_solution()
        root = TreeNode(0, 0, 0, [])

        stack = [root]

        while len(stack) > 0:

            current = stack.pop()    
            index   = current.level

            if current.V >= best.V:         # consider whether we can immediately improve our best
                best = current

            if index < len(self.values):    # there are items left to consider

                
                # we have two branches to consider: if we have room, we take the item
                # if we don't have room, we continue our solution to the next iteration 
                # where we consider the next item

                if current.W + self.weights[index] <= self.capacity:
                    taken = list(current.taken)     # update path of items taken
                    taken.append(index)
                                                    # create the right node
                    right = TreeNode( index + 1, current.V + self.values[index],
                                  current.W + self.weights[index], taken )

                    if right.V > best.V:            # update our best, if possible 
                        best = right
                
                    bound = self._linear_relaxation(index, right.V, right.W)

                                                    # only continue exploring if 
                                                    # we're guaranteed something better
                    if bound >= best.V:
                        stack.append(right)

                                                    # create the left node, continue
                                                    # solution of the parent, without             
                                                    # taking the item 

                left  = TreeNode( index + 1, current.V, current.W, list(current.taken) )
                bound = self._linear_relaxation(index, left.V, left.W)

                                                    # only continue exploring if 
                                                    # we're guaranteed something better
                if bound >= best.V:                 
                    stack.append(left)

               
        return best