动态规划:背包问题

动态规划，都可以画网格解决！

背包问题

假设你是个小偷，背着一个可装4 磅东西的背包。
你可盗窃的商品有如下3 件：
音响，3000美元，4磅
笔记本电脑，2000美元，3磅
吉他，1500美元，1磅

image.png

 #author: Jingke

def bag(goods):
    cell = [[0, 0, 0, 0],
            [0, 0, 0, 0],
            [0, 0, 0, 0]]
    package_size = [1, 2, 3, 4]

    for j in range(4):
        if goods[0][1] <= package_size[j]:
            cell[0][j] = goods[0][0]
            # print(cell[0][j])

    for i in range(1, 3):
        """i=1,2"""
        for j in range(4):
            if goods[i][1] == package_size[j] and goods[i][0] >= cell[i - 1][j]:
                cell[i][j] = goods[i][0]
            elif goods[i][1] == package_size[j] and goods[i][0] < cell[i - 1][j]:
                cell[i][j] = cell[i - 1][j]
            elif goods[i][1] > package_size[j]:
                cell[i][j] = cell[i - 1][j]
            elif goods[i][1] < package_size[j]:
                a = package_size[j] - goods[i][1] #a=3
                b = cell[i-1][a-1] + goods[i][0]
                if b >= cell[i - 1][j]:
                    cell[i][j] = b
                else:
                    cell[i][j] = cell[i - 1][j]
    return cell

goods = [[2000, 3],
         [1500, 1],
         [3000, 4]]

print(bag(goods))
print(bag(goods)[2][3])

#[[0, 0, 2000, 2000], [1500, 1500, 2000, 3500], [1500, 1500, 2000, 3500]]
#3500