I have this algorithm with this piece of recursive code that basically is a solution to the knapsack problem via brute force.
Where I have a calorie limit of 750, and so I want to find a collection of foods that have the highest total value while staying below or equal to 750 calories.
However I do not understand the algorithm.
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):
if toConsider == [] or avail == 0:
result = (0, ())
elif toConsider[0].getCost() > avail:
result = maxVal(toConsider[1:], avail)
else:
nextItem = toConsider[0]
withVal, withToTake = maxVal(toConsider[1:],
avail - nextItem.getCost())
withVal += nextItem.getValue()
withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
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)
names = ['wine', 'beer', 'pizza', 'burger', 'fries',
'cola', 'apple', 'donut', 'cake']
values = [89, 90, 95, 100, 90, 79, 50, 10]
calories = [123, 154, 258, 354, 365, 150, 95, 195]
foods = buildMenu(names, values, calories)
print('')
testMaxVal(foods, 750)
When I put
print(toConsider)
under the first line of code here so that I can see the size of the list, I notice it fluctuates.
But what I'm seeing is, if you imagine 'toConsider' to be a list, is that as soon as it hits
withVal, withToTake = maxVal(toConsider[1:],
avail - nextItem.getCost())
or if it satisfies
elif toConsider[0].getCost() > avail:
it will take 1 away from the list at a time basically, either way the list is going to be reduced by 1, recursively or not, every time consistently until the list is nothing.
In which this case
if toConsider == [] or avail == 0:
result = (0, ())
will activate and supposedly our answer would be that because at the bottom there is a return result, however the program doesn't end there which is where I'm confused as the size of 'toConsider' fluctuates when it should be nothing.
My confusion is that even though return is (0, ()) at one point, and toConsider is []
a. how is the program still continuing to run after the 'return' in the code which also causes...(the statement below)
b. how is toConsider able to somehow 'regenerate' some of the elements back.
because the output is
Use search tree to allocate 750 calories
Total value of items taken = 353
cola: <79, 150>
pizza: <95, 258>
beer: <90, 154>
wine: <89, 123>
whereas if I look at the code, and visualising it on python tutor I expect
(0,())
What I have tried:
I have tried using programming tutor to solve my problem however, once it gets to step 199, toConsider suddenly has a donut in it! i.e an element. When it should have none. Here's the link
Submit an article or tip