How does a short recursive maxVal search the whole knapsack tree without ever building it, and where does it hit an exponential wall?
Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.
Each call of maxVal(toConsider, avail) is one node of the search tree, and it makes either 0, 1 or 2 recursive calls: none when there is nothing left to decide or no room left, one when the first item cannot fit, two when it can. Items are Food objects (the class is given), so an item's weight is getCost(). Define branchesToExplore(toConsider, avail) that returns how many recursive calls that node makes.
class Food(object):
def __init__(self, n, v, w):
self.name = n
self.value = v
self.calories = w
def getValue(self):
return self.value
def getCost(self):
return self.calories
def density(self):
return self.getValue()/self.getCost()
def __str__(self):
return f'{self.name}: <{self.value}, {self.calories}>'
def buildMenu(names, values, calories):
menu = []
for i in range(len(values)):
menu.append(Food(names[i], values[i], calories[i]))
return menu