9动态规划

1.背包问题

1.简单算法

最简单的算法：尝试各种可能的商品组合，并找出价值最高的组合。
缺点：速度非常慢。3种商品需要计算8种组合；4件商品是，需要计算16中组合。每增加一种商品，需要计算的集合数将翻倍。这种算法的运行时间为O(2ⁿ)

2. 动态规划

使用动态规划可以得到最优解。

实现

bag={
    "computer":{"weight":3,"value":2000},
    "guitar":{"weight":1,"value":1500},
    "sound":{"weight":4,"value":3000}
}
list=[]
goods = []
row=0
def addList(list1,list2):
    for i in list1:
        list2.append(i)
for key in bag.keys():
    sublist=[]
    subGood=[]
    keyWeight = bag.get(key)["weight"]
    keyValue = bag.get(key)["value"]
    for column in range(4):
        sub=[]
        #单元格 = 列的索引+1
        weight = column + 1
        #判断行，行数=0，直接对比；行数大于0，与上一行进行对比
        if(row > 0):
            if(weight < keyWeight):
                sublist.append(list[row-1][column])
                addList(goods[row - 1][column], sub)
            elif(weight == bag.get(key)["weight"]):
                if( list[row-1][column] < keyValue ):
                    sublist.append(keyValue)
                    sub.append(key)
                else:
                    sublist.append(list[row-1][column])
                    addList(goods[row-1][column],sub)
            else:
                #如果单元格重量>商品，就判断商品的权重和同位置大小
                #判断weight-bag.get(key)["weight"]
                if (list[row-1][column] < ( keyValue + list[row-1][weight-keyWeight-1] ) ):
                    sublist.append( keyValue + list[row-1][weight-keyWeight-1])
                    sub.append(key)
                    addList(goods[row - 1][weight-keyWeight-1], sub)
                else:
                    sublist.append(list[row-1][column])
                    addList(goods[row-1][column],sub)
        else:
            #直接判断，单元格 < 物品重量
            if(weight < keyWeight):
                sublist.append(0)
                # sub.append([])
            else:
                sublist.append(keyValue)
                sub.append(key)
        subGood.append(sub)
    list.append(sublist)
    goods.append(subGood)
    row+=1
#最大值肯定在最后一组，获取最大值的索引
print("4斤背包容纳的最大价值组合：%s %s" % (list[-1][max_index],goods[-1][max_index]))    #4斤背包容纳的最大价值组合：3500 ['guitar', 'computer']

9动态规划

原文：https://www.cnblogs.com/csj2018/p/12173574.html