15,877,966 members
See more:
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.

Python
```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) + '>'

for i in range(len(values)):
calories[i]))

#This is where I'm getting confused
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]

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

Posted
Member 13615317 10-Jan-18 1:33am
I attached a link, that didn't show up.

He it is but it's quite long sorry