I'm attempting to solve the classic knapsack problem using decision trees and getting stuck with an error. I tried playing around with the print statements and got information that one of the helper function is not working correctly but I'm unable to rectify it. Can someone help?
Posting my original code:
class BinaryTree(object): def __init__(self,value): self.value = value self.leftBranch = None self.rightBranch = None self.parent = None def setLeftBranch(self,node): self.leftBranch = node def setRightBranch(self,node): self.rightBranch = node def setParent(self,parent): self.parent = parent def getValue(self): return self.value def getLeftBranch(self): return self.leftBranch def getRightBranch(self): return self.rightBranch def getParent(self): return self.parent def __str__(self): return self.value def buildDTree(sofar,todo): '''sofar: list of things that I have already decided to add when I got to this node. todo: list of things I still have to consider ''' if len(todo) == 0: return BinaryTree(sofar) else: withelt = buildDTree(sofar +todo, todo[1:]) withoutelt = buildDTree(sofar, todo[1:]) here = BinaryTree(sofar) here.setLeftBranch(withelt) here.setRightBranch(withoutelt) return here def DFSDTree(root,valueFcn, constraintFcn): stack = [root] visited = 0 best = None while len(stack) > 0: visited += 1 print stack.getValue() if constraintFcn(stack.getValue()): if best == None: best = stack elif valueFcn(stack.getValue()) > valueFcn(best.getValue()): best = stack temp = stack.pop(0) if temp.getRightBranch(): stack.insert(0,temp.getRightBranch()) print stack.getValue() if temp.getLeftBranch(): stack.insert(0,temp.getLeftBranch()) print stack.getValue() else: stack.pop(0) print 'visited', visited return best def sumValues(lst): vals = [e for e in lst] return sum(vals) def WeightsBelow10(lst): wts = [e for e in lst] #print type(wts) #print wts return sum(wts) <= 10
Here's how I'm testing it. What I can clearly see is that when [6,3] is passed to the constraintFcn as an argument, the constraintFcn which is WeightsBelow10 isn't able to execute because the line wts = [e for e in lst] doesn't work as there is no indexing possible with 3 which is of type int and not a list. How do we rectify this?
foo = DFSDTree(treeTest, sumValues, WeightsBelow10)   [6, 3] [6, 3] Traceback (most recent call last): File "<ipython-input-33-f01be6de33be>", line 1, in <module> foo = DFSDTree(treeTest, sumValues, WeightsBelow10) File "C:/Users/pvatsa/.spyder2/6.00.1x Files/knapsack_problem.py", line 61, in DFSDTree if constraintFcn(stack.getValue()): File "C:/Users/pvatsa/.spyder2/6.00.1x Files/knapsack_problem.py", line 83, in WeightsBelow10 wts = [e for e in lst] TypeError: 'int' object has no attribute '__getitem__'