def trace(f):
    indent = 0
    
    def wrapper(*args):
        nonlocal indent

        spaces = '|  ' * indent 
        arg_str = ', '.join(map(repr, args))
        print(spaces + f'{f.__name__}({arg_str})')
        indent += 1
        result = f(*args)
        indent -= 1
        print(spaces + f'> {result}')
        return result

    return wrapper

def memoize(f):
    answers = {}  # answers[args] = f(*args) 
    
    def wrapper(*args):
        if args not in answers:
            answers[args] = f(*args)
        return answers[args]

    return wrapper

def knapsack_value(volume, value, capacity):
    @memoize
    def solve(c, k):
        if k == 0:
            return 0
        v = solve(c, k-1)
        if volume[k-1] <= c:
            v = max(v, value[k-1] + solve(c - volume[k-1], k - 1))
        return v

    return solve(capacity, len(volume))

@trace
def knapsack(volume, value, capacity):
    @memoize
    @trace
    def solve(c, k):
        if k == 0:
            return 0, []
        v, solution = solve(c, k-1)
        if volume[k-1] <= c:
            v2, sol2 = solve(c - volume[k-1], k - 1)
            v2 = v2 + value[k-1]
            if v2 > v:
                v = v2
                solution = sol2 + [k - 1]
        return v, solution

    return solve(capacity, len(volume))

volumes = [3, 3, 2, 5]
values = [6, 7, 8, 9]

print(knapsack_value(volumes, values, 5))
print(knapsack(volumes, values, 5))