背包问题

N = 3   # 物品数量
W = 10  # 限制重量
weights = [3, 4, 5]      # 重量
values = [4, 5, 6]    # 价值
F = [[0 for i in range(0, W + 1)] for _ in range(N)]  # N 行, W 列
print("0\t", *list(range(0, W + 1)), sep="\t")
for k in range(0, N):
    for c in range(0, W + 1):
        if weights[k] > c:
            F[k][c] = F[k - 1][c]
            continue
        v1 = F[k - 1][c - weights[k]] + values[k]
        v2 = F[k - 1][c]
        F[k][c] = max(v1, v2)
    print(f"{k+1}-{weights[k]}-{values[k]}", *F[k], sep="\t")
print(F[N - 1][W - 1])

背包问题九讲V2.pdf