猿问

关于隐式决策树解决背包的问题??

关于这段代码我知道原理,但是我无法正确的表达出代码运作的细节!不知道怎么往下走,为此画了一个图,比较简陋,将就看一下吧。。。。。。。。

请前辈提示我:
1.withVal 和 withoutVal两个值为什么是图上左边框框里的数值?我自己按照自己的理解在右边的树上标注了出来,但是和答案不一样,我不理解!
2.正确的流线是怎么走的,我已标注好左背包和右背包的流线序号!

以下是python代码:

a = [6,3]
b = [7,2]
c = [8,4]
d = [9,5]
def DTImplicit(toConsider, avail):
    if toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider[0][1] > avail:
        result = DTImplicit(toConsider[1:], avail)
    else:
        nextItem = toConsider[0]
        withVal, withToTake = DTImplicit(toConsider[1:], avail - nextItem[1])
        withVal += nextItem[0]
        withoutVal, withoutToTake = DTImplicit(toConsider[1:], avail)
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)

    return result

    
stuff = [[6,3],[7,2],[8,4],[9,5]]
val, taken = DTImplicit(stuff, 10)
print val
print taken

以下是图:

asdhjhg
浏览 1422回答 0
0回答
随时随地看视频慕课网APP

相关分类

Python
我要回答