0/1 Knapsack

Given positive integer weights, nonnegative integer values of equal length, and capacity >= 0, return the largest value of a subset whose total weight is at most capacity. Each indexed item can be used at most once, including when multiple items have equal weight/value. Empty input returns 0. At most 100 items and capacity <= 1000. Examples (JSON; null means Python None): Input: {"weights": [2, 3, 4], "values": [4, 5, 7], "capacity": 5} Output: 9 Input: {"weights": [2], "values": [3], "capacity": 4} Output: 3

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    """Choose each item at most once within a weight budget."""
    pass