Я не понимаю рекурсии в этом фрагменте кода
У меня есть этот алгоритм с этим фрагментом рекурсивного кода, который в основном является решением проблемы рюкзака с помощью грубой силы.
Где у меня есть лимит калорий 750, и поэтому я хочу найти коллекцию продуктов, которые имеют самую высокую общую ценность, оставаясь ниже или равными 750 калориям.
Однако я не понимаю этого алгоритма.
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)
Когда я положил
print(toConsider)под первой строкой кода здесь, чтобы я мог видеть размер списка, я замечаю, что он колеблется.
Но то, что я вижу, если вы представляете себе "toConsider" как список, это то, что сразу же попадает в него
withVal, withToTake = maxVal(toConsider[1:],
avail - nextItem.getCost())
или если это удовлетворяет
elif toConsider[0].getCost() > avail:
это будет отнимать 1 из списка за один раз в основном, в любом случае список будет уменьшен на 1, рекурсивно или нет, каждый раз последовательно, пока список не станет ничем.
В каком это случае
if toConsider == [] or avail == 0:
result = (0, ())
активируется, и предположительно наш ответ будет таков, потому что внизу есть обратный результат, однако программа на этом не заканчивается, и именно здесь я запутался, так как размер "toConsider" колеблется, когда он должен быть ничем.
Моя путаница заключается в том, что даже если return равен (0, ()) в одной точке, а toConsider-это []
а. как программа все еще продолжает работать после "возврата" в коде, который также вызывает...(заявление ниже)
b. как toConsider может каким-то образом "регенерировать" некоторые элементы обратно.
потому что выход есть
Используйте дерево поиска, чтобы выделить 750 калорий
Общая стоимость взятых предметов = 353
Кола: <79, 150>
пицца: <95, 258>
пиво: <90, 154>
вино: <89, 123>
в то время как если я посмотрю на код и визуализирую его на python tutor, я ожидаю, что
(0,())
Что я уже пробовал:
Я попытался использовать programming tutor для решения своей проблемы, однако, как только она доходит до шага 199, toConsider внезапно имеет в себе пончик! то есть элемент. Когда у него ничего не должно быть. Вот ссылка
Member 13615317
Я прикрепил ссылку, но она не появилась.
Он так и есть но это довольно долго извините
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