"""
背包练习2021/12/9号李兴球
假设你是一个计算机科学家或是一个艺术小偷，闯入了一个艺术画廊。
你身上只有一个背包可以用来偷出宝物，这个背包只能装W英镑的艺术品，
但你知道每一件艺术品的价值和它的重量。运用动态规划写一个函数，
来帮助你获得最多价值的宝物。假设你的背包可以容纳的总重量为20，你有如下5件宝物：
重量为2价值为3，重量为3价值为4，重量为4价值为8，重量为5价值为8，重量为8价值为10。
"""
stuffs = {1:(2,3),2:(3,4),3:(4,8),4:(5,8),5:(9,10)} # 宝物字典
def max_values(arts,maxweight):
"""arts就是艺术品存储的数据结构,这里用的字典表示,maxweight就是背包能装的最大重量
placed表示已经装好的宝物
"""
r = []
for k,v in arts.items(): # 最后一个每个都试下
placed = arts.copy() # 保存备份,(因为arts进行pop的话会越来越少东西
w,p = placed.pop(k) # 弹出一个东西
if maxweight-w>=0: # 如果背包还能放得下这个宝物
v = max_values(placed,maxweight-w) # 则求已经放置的那些宝物的最大值
else:
return 0
r.append( p+v) # 由于还能放得下,所以p+v就是一种方案的价值
if r: return max(r)
return 0
#print(max_values(stuffs,20))
# 减法
def schemes(arts,maxweight):
"""解题思想是把所有的宝物都试图放在虚拟背包里,然后做减法,每个宝物都拿掉，算下新的重量有多少。
如果新的重量小于等于背包能装的最大重量,说明剩下所有的宝物就是一种可能的方案。
如果新的重量仍旧大于背包能装的最大重量，还需要继续减。
"""
global scheme # 全局变量可以去掉，请自行优化
total_weight = sum([value[0] for value in arts.values()]) # 当前虚拟背包的总重量
for i in arts: # 每个宝物都试图拿掉
w = total_weight - arts[i][0] # 减去宝物i的重量
placed = arts.copy() # 已放置的
placed.pop(i) # 拿出一个来
if w <= maxweight : # 如果剩下的总重量w小于等于背包能装的最大重量,说明是一种方案
scheme.append(placed) # 把这种方案保存起来
else: # 还要减
schemes(placed,maxweight) # 否则,已装在虚拟背包里的宝物总重量w仍大于背包能装的最大重量,继续做减法
scheme = []
schemes(stuffs,20)
for sc in scheme:
print(sc)
print(sum([value[0] for value in sc.values()]))
print()
