0:1 bottom up
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