3.2 举例:0-1背包问题
3.2.1 问题描述
你现在想买⼀大堆算法书,有一个容量为 V 的背包,这个商店⼀共有 n 个商品。问题在于,你最多只能拿 W kg 的东西,其中 wi 和 vi 分别表示第 i 个商品的重量和价值。最终的目标就是在能拿的下的情况下,获得最大价值,求解哪些物品可以放进背包。
def knapsack():
for w in range(W+1):
cache[get_key(0,w)] = 0
for i in items:
cache[get_key(i,0)] = 0
for w in range(W+1):
if w >= weights[i]:
if cache[get_key(i-1,w-weights[i])] + values[i] > cache[get_key(i-1,w)]:
cache[get_key(i,w)] = values[i] + cache[get_key(i-1,w-weights[i])]
else:
cache[get_key(i,w)] = cache[get_key(i-1,w)]
else:
cache[get_key(i,w)] = cache[get_key(i-1,w)]
return cache[get_key(8,W)]
def get_key(i,w):
return str(i)+','+str(w)
if __name__ == '__main__':
# 背包把所有东西都能装进去做假设开始
print(knapsack())
29
>>>