text: 
  
  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 self.name + ': <' + str(self.value)\
                   + ', ' + str(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
  
  def maxVal(toConsider, avail):
      """Assumes toConsider a list of items, avail a weight
         Returns a tuple of the total weight of a solution to the
           0/1 knapsack problem and the items of that solution"""
      if toConsider == [] or avail == 0:
          result = (0, ())
      elif toConsider[0].getCost() > avail:
          #Explore right branch only
          result = maxVal(toConsider[1:], avail)
      else:
          nextItem = toConsider[0]
          #Explore left branch
          withVal, withToTake = maxVal(toConsider[1:],
                                       avail - nextItem.getCost())
          withVal += nextItem.getValue()
          #Explore right branch
          withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
          #Choose better branch
          if withVal > withoutVal:
              result = (withVal, withToTake + (nextItem,))
          else:
              result = (withoutVal, withoutToTake)
      return result
  
  def testMaxVal(foods, maxUnits, printItems = True):
      print('Use search tree to allocate', maxUnits,
            'calories')
      val, taken = maxVal(foods, maxUnits)
      print('Total value of items taken =', val)
      if printItems:
          for item in taken:
              print('   ', item)
  
  
  import random
  
  def buildLargeMenu(numItems, maxVal, maxCost):
      items = []
      for i in range(numItems):
          items.append(Food(str(i),
                            random.randint(1, maxVal),
                            random.randint(1, maxCost)))
      return items
  
  for numItems in (5, 10, 15, 20, 25, 30, 35, 40, 45):
      print('\nTry a menu with', numItems, 'items')
      items = buildLargeMenu(numItems, 90, 250)
      testMaxVal(items, 750, False)
      
  
  def fib(n):
      if n == 0 or n == 1:
          return 1
      else:
          return fib(n - 1) + fib(n - 2)
  
  # for i in range(121):
  #     print('fib(' + str(i) + ') =', fib(i))
  
  
  def fastFib(n, memo = {}):
      """Assumes n is an int >= 0, memo used only by recursive calls
         Returns Fibonacci of n"""
      if n == 0 or n == 1:
          return 1
      try:
          return memo[n]
      except KeyError:
          result = fastFib(n-1, memo) + fastFib(n-2, memo)
          memo[n] = result
          return result
  
  #for i in range(121):
  #    print('fib(' + str(i) + ') =', fastFib(i))
  
  