Python算法（进阶）

1. 01背包问题

有若干物品,每个物品有对应的重量weight和价值value,背包容纳重量为bag_weight,在背包允许的重量下,往背包内放物品,每个物品只能放一次,保证其价值最高

weight = [2,2,6,5,4]                      # 物品重量列表
value = [3,6,5,4,6]                        # 物品价值列表
bag_weight = 10                           # 背包容纳重量

def fullBag(weight, value, bag_weight):
    num = len(weight)            # 获取物品数量
    weight.insert(0,0)            # 不存在第0个物品，第0个总重量为0
    value.insert(0,0)                # 同上
    # 使用numpy快速建立数组，即六种情况，一个不取、只选择第一个，只选择前两个...全部进行选择等情况的数组
    bag = np.zeros((num + 1, bag_weight + 1), dtype=np.int32)
    # 循环取值，i和j分别对应行和列
    for i in range(1,num+1):
        for j in range(1,bag_weight+1):
            if weight[i] <= j:
                bag[i][j] = max(bag[i-1][j-weight[i]]+value[i],bag[i-1][j])
            else:
                bag[i][j] = bag[i-1][j]
    print(bag)
    return bag[-1,-1]

result = fullBag(weight,value,bag_weight)
print(result)