背包练习2021/12/9

"""
   背包练习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()