# Author: ChatGPT 5.0

def knapsack_recursive(weights, values, capacity, n, memo):
    """
    Recursive solution for the 0/1 Knapsack problem with memoization.

    Parameters:
        weights (list[int]): Item weights.
        values (list[int]): Item values.
        capacity (int): Remaining capacity of the knapsack.
        n (int): Number of items left to consider.
        memo (dict): Cache for memoization (key: (n, capacity)).

    Returns:
        int: Maximum total value for the given parameters.
    """
    # Base case: no items left or no remaining capacity
    if n == 0 or capacity == 0:
        return 0

    # Check if already computed
    if (n, capacity) in memo:
        return memo[(n, capacity)]

    # If item weight exceeds current capacity, skip it
    if weights[n - 1] > capacity:
        result = knapsack_recursive(weights, values, capacity, n - 1, memo)
    else:
        # Option 1: Include the item
        include = values[n - 1] + knapsack_recursive(weights, values, capacity - weights[n - 1], n - 1, memo)
        # Option 2: Exclude the item
        exclude = knapsack_recursive(weights, values, capacity, n - 1, memo)
        # Choose the better of the two options
        result = max(include, exclude)

    # Store result in memo before returning
    memo[(n, capacity)] = result
    return result


# Example usage
if __name__ == "__main__":
    values = [60, 100, 120]
    weights = [10, 20, 30]
    capacity = 50
    n = len(values)
    memo = {}

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