0:1 bottom up

 avatar
unknown
python
a year ago
425 B
5
Indexable
def knapsackBottomUp(n: int, values: List, weights: List, W: int) -> int:
    T = [[None] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            index = i - 1
            if weights[index] <= w:
                T[i][w] = max(values[index] + T[i - 1][w - weights[index]], T[i - 1][w])
            else:
                T[i][w] = T[i - 1][w]

    return T[n][W]
Editor is loading...
Leave a Comment