Click here to Skip to main content
15,877,966 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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) + '>'


def buildMenu(names, values, calories):
    menu = []
    for i in range(len(values)):
        menu.append(Food(names[i], values[i],
                         calories[i]))
    return menu

#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]
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

Posted
Comments
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

http://www.pythontutor.com/live.html#code=class%20Food%28object%29%3A%0A%20%20%20%20def%20__init__%28self,%20n,%20v,%20w%29%3A%0A%20%20%20%20%20%20%20%20self.name%20%3D%20n%0A%20%20%20%20%20%20%20%20self.value%20%3D%20v%0A%20%20%20%20%20%20%20%20self.calories%20%3D%20w%0A%0A%20%20%20%20def%20getValue%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20self.value%0A%0A%20%20%20%20def%20getCost%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20self.calories%0A%0A%20%20%20%20def%20density%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20self.getValue%28%29%20/%20self.getCost%28%29%0A%0A%20%20%20%20def%20__str__%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20self.name%20%2B%20'%3A%20%3C'%20%2B%20str%28self.value%29%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B%20',%20'%20%2B%20str%28self.calories%29%20%2B%20'%3E'%0A%0A%0Adef%20buildMenu%28names,%20values,%20calories%29%3A%0A%20%20%20%20menu%20%3D%20%5B%5D%0A%20%20%20%20for%20i%20in%20range%28len%28values%29%29%3A%0A%20%20%20%20%20%20%20%20menu.append%28Food%28names%5Bi%5D,%20values%5Bi%5D,%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20calories%5Bi%5D%29%29%0A%20%20%20%20return%20menu%0A%0A%0Adef%20maxVal%28toConsider,%20avail%29%3A%0A%20%20%20%20if%20toConsider%20%3D%3D%20%5B%5D%20or%20avail%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20result%20%3D%20%280,%20%28%29%29%0A%0A%20%20%20%20elif%20toConsider%5B0%5D.getCost%28%29%20%3E%20avail%3A%0A%0A%20%20%20%20%20%20%20%20result%20%3D%20maxVal%28toConsider%5B1%3A%5D,%20avail%29%0A%20%20%20%20else%3A%0A%0A%20%20%20%20%20%20%20%20nextItem%20%3D%20toConsider%5B0%5D%0A%0A%20%20%20%20%20%20%20%20withVal,%20withToTake%20%3D%20maxVal%28toConsider%5B1%3A%5D,%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20avail%20-%20nextItem.getCost%28%29%29%0A%0A%20%20%20%20%20%20%20%20withVal%20%2B%3D%20nextItem.getValue%28%29%0A%0A%20%20%20%20%20%20%20%20withoutVal,%20withoutToTake%20%3D%20maxVal%28toConsider%5B1%3A%5D,%20avail%29%0A%0A%20%20%20%20%20%20%20%20if%20withVal%20%3E%20withoutVal%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20result%20%3D%20%28withVal,%20withToTake%20%2B%20%28nextItem,%29%29%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20result%20%3D%20%28withoutVal,%20withoutToTake%29%0A%20%20%20%20return%20result%0A%0A%0Adef%20testMaxVal%28foods,%20maxUnits,%20printItems%3DTrue%29%3A%0A%20%20%20%20print%28'Use%20search%20tree%20to%20allocate',%20maxUnits,%0A%20%20%20%20%20%20%20%20%20%20'calories'%29%0A%20%20%20%20val,%20taken%20%3D%20maxVal%28foods,%20maxUnits%29%0A%20%20%20%20print%28'Total%20value%20of%20items%20taken%20%3D',%20val%29%0A%20%20%20%20if%20printItems%3A%0A%20%20%20%20%20%20%20%20for%20item%20in%20taken%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%28'%20%20%20',%20item%29%0A%0A%0Anames%20%3D%20%5B'wine',%20'beer',%20'pizza',%20'burger',%20'fries',%0A%20%20%20%20%20%20%20%20%20'cola',%20'apple',%20'donut',%20'cake'%5D%0Avalues%20%3D%20%5B89,%2090,%2095,%20100,%2090,%2079,%2050,%2010%5D%0Acalories%20%3D%20%5B123,%20154,%20258,%20354,%20365,%20150,%2095,%20195%5D%0Afoods%20%3D%20buildMenu%28names,%20values,%20calories%29%0A%0Aprint%28''%29%0AtestMaxVal%28foods,%20750%29&cumulative=false&curInstr=999&heapPrimitives=false&mode=display&origin=opt-live.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900