其中视频动态规规划里面的关于斐波拉契数列momorize的函数比较印象深刻
In [1]: def maxVal(toConsider, avail):
...: """假设toConsider是一个物品列表， avail表示重量
...: 返回一个元组表示0/1背包问题的解，包括物品总价值和物品列表"""
...: if toConsider == [] or avail == 0:
...: result = (0, ())
...: elif toConsider[0].getWeight() > avail:
...: #探索右侧分支
...: result = maxVal(toConsider[1:], avail)
...: else:
...: nextItem = toConsider[0]
...: #探索左侧分支
...: withVal, withToTake = maxVal(toConsider[1:],
...: avail - nextItem.getWeight())
...: withVal += nextItem.getValue()
...: #探索右侧分支
...: withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
...: #选择更好的分支
...: if withVal > withoutVal:
...: result = (withVal, withToTake + (nextItem,))
...: else:
...: result = (withoutVal, withoutToTake)
...: return result
In [8]: class Item(object):
...: def __init__(self, n, v, w):
...: self.name = n
...: self.value = v
...: self.weight = w
...: def getName(self):
...: return self.name
...: def getValue(self):
...: return self.value
...: def getWeight(self):
...: return self.weight
...: def __str__(self):
...: result = '<' + self.name + ', ' + str(self.value)\
...: + ', ' + str(self.weight) + '>'
...: return result
...:
...: def value(item):
...: return item.getValue()
...:
...: def weightInverse(item):
...: return 1.0/item.getWeight()
...:
...: def density(item):
...: return item.getValue()/item.getWeight()
In [9]: def smallTest():
...: names = ['a', 'b', 'c', 'd']
...: vals = [6, 7, 8, 9]
...: weights = [3, 3, 2, 5]
...: Items = []
...: for i in range(len(vals)):
...: Items.append(Item(names[i], vals[i], weights[i]))
...: val, taken = maxVal(Items, 5)
...: for item in taken:
...: print(item)
...: print('Total value of items taken =', val)
...:
In [10]: smallTest()
<c, 8, 2>
<b, 7, 3>
Total value of items taken = 15
In [3]:
...: def buildManyItems(numItems, maxVal, maxWeight):
...: items = []
...: for i in range(numItems):
...: items.append(Item(str(i),
...: random.randint(1, maxVal),
...: random.randint(1, maxWeight)))
...: return items
...:
In [4]: def bigTest(numItems):
...: items = buildManyItems(numItems, 10, 10)
...: val, taken = maxVal(items, 40)
...: print('Items Taken')
...: for item in taken:
...: print(item)
...: print('Total value of items taken =', val)
In [12]: import random
In [13]: bigTest(40)
Items Taken
<33, 10, 5>
<32, 10, 3>
<31, 3, 3>
<29, 10, 6>
<28, 3, 1>
<24, 10, 3>
<21, 9, 2>
<17, 10, 4>
<14, 8, 3>
<9, 7, 1>
<2, 9, 3>
<0, 10, 6>
Total value of items taken = 99
In [15]: def fastMaxVal(toConsider, avail, memo = {}):
...: """假设toConsider是物品列表， avail表示重量
...: memo进行递归调用
...: 返回一个元组表示0/1背包问题的解，包括物品总价值和物品列表"""
...: if (len(toConsider), avail) in memo:
...: result = memo[(len(toConsider), avail)]
...: elif toConsider == [] or avail == 0:
...: result = (0, ())
...: elif toConsider[0].getWeight() > avail:
...: #探索右侧分支
...: result = fastMaxVal(toConsider[1:], avail, memo)
...: else:
...: nextItem = toConsider[0]
...: #探索左侧分支
...: withVal, withToTake =\
...: fastMaxVal(toConsider[1:],
...: avail - nextItem.getWeight(), memo)
...: withVal += nextItem.getValue()
...: #探索右侧分支
...: withoutVal, withoutToTake = fastMaxVal(toConsider[1:],
...: avail, memo)
...: #选择更好的分支
...: if withVal > withoutVal:
...: result = (withVal, withToTake + (nextItem,))
...: else:
...: result = (withoutVal, withoutToTake)
...: memo[(len(toConsider), avail)] = result
...: return result
...:
