关于这段代码我知道原理,但是我无法正确的表达出代码运作的细节!不知道怎么往下走,为此画了一个图,比较简陋,将就看一下吧。。。。。。。。
请前辈提示我:
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
以下是图:
相关分类