关于下面的代码,我遇到了一道理解墙。它的目的是在一个既有个人效用又有成本的项目列表中进行搜索,就好像它在一个可能项目的二叉搜索树中寻找一个最优的解决方案一样。具体地说,它考虑了通过组合这些项可以获得的最大效用,受传递到函数中的权重约束的约束。你知道吗
else语句下的第一个递归调用是问题开始的地方。一旦进行了初始递归调用,并将值抛出到withVal和withToTake中,代码是否继续递归(堆积堆栈帧直到命中基本情况),还是继续到代码的底部,然后考虑递归调用?打印报表对这件事毫无帮助。任何洞察都将不胜感激!你知道吗
def maxVal(toConsider, avail):
'''Assumes toConsider is a list of items (nodes higher up in the tree
corresponding to earlier calls in the recursive stack. That have not
yet been considered. avail a weight (amt of space still available).
Returns a tuple of the total value of a solution to the 0/1
knapsack problem and the items of that solution.
*Note we are NOT building the search tree. The local variable
result returns the best result found so far.To be used with
food class*
'''
#Base Cases: Nothing left to consider, or available weight is 0
if toConsider == [] or avail == 0:
result = (0, ())
#look at the first item's weight in toConsider & check against available space
#if the item's weight is > avail, recurse and slice off the first item
elif toConsider[0].getCost() > avail:
result = maxVal(toConsider[1:], avail)
else:
#look at left branch
nextItem = toConsider[0]
**withVal, withToTake = maxVal(toConsider[1:], avail - nextItem.getCost())**
withVal += nextItem.getValue()
#look at right branch
withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
#tests whether left or right branch is better
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withToTake)
return result
toCosider将获取具有效用值的食物对象列表&maxUnits是一个任意整数,表示可以携带的最大食物量。你知道吗
目前没有回答
相关问题 更多 >
编程相关推荐