# Author: ChatGPT 5.0

def knapsack(weights, values, capacity):
    """
    Solve the 0/1 Knapsack problem using Dynamic Programming.

    Parameters:
        weights (list[int]): The weights of the items.
        values (list[int]): The values (profits) of the items.
        capacity (int): The maximum weight the knapsack can hold.

    Returns:
        int: The maximum total value that can be put in the knapsack.
    """

    n = len(values)
    # dp[i][w] = maximum value achievable with first i items and capacity w
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    # Build dp table
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                # Option 1: include the item
                include = values[i - 1] + dp[i - 1][w - weights[i - 1]]
                # Option 2: exclude the item
                exclude = dp[i - 1][w]
                dp[i][w] = max(include, exclude)
            else:
                dp[i][w] = dp[i - 1][w]

    print( dp )

    # dp[n][capacity] contains the answer
    return dp[n][capacity]


# Example usage
if __name__ == "__main__":
    values = [60, 100, 120]
    weights = [10, 20, 30]
    capacity = 50

    max_value = knapsack(weights, values, capacity)
    print(f"Maximum value in knapsack = {max_value}")