# Title: 0/1 knapsack
# Heading: Python Program for the 0/1 Knapsack Problem
# Level: advanced
# Tags: knapsack problem, 0/1 knapsack, dynamic programming, dp
# Time: O(n × W)
# Space: O(n × W)
# About: Finds the most value that fits in a bag with a weight limit, taking each item at most once, by filling in a table.

def knapsack(weights, values, capacity):
    """The most value that fits, taking each item at most once."""
    n = len(weights)
    # best[i][w]: the most value from the first i items in weight w
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            best[i][w] = best[i - 1][w]  # without item i
            if weight <= w:  # with item i, if it fits
                with_item = best[i - 1][w - weight] + value
                best[i][w] = max(best[i][w], with_item)
    return best[n][capacity]


weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print("Best value for capacity 7:", knapsack(weights, values, 7))