Наша цель — выбрать список не более чем из k разных проектов, чтобы максимизировать окончательный капитал и вернуть этот максимальный капитал.

В чем проблема спросить?

Основная проблема заключается в том, что для запуска каждого проекта требуется минимальный капитал, а мы ограничены начальным капиталом w. Кроме того, мы можем завершить только ограниченное количество проектов k.

Нам нужно делать выбор, который постепенно максимизирует наш капитал, будучи ограниченным объемом капитала, который у нас есть на каждом этапе.

Подход:

  1. Отсортируйте проекты на основе их требований к капиталу. Это поможет нам эффективно проверять, какие проекты мы можем себе позволить в любой момент.
  2. Используйте максимальную кучу, чтобы отслеживать самые прибыльные проекты, которые мы можем себе позволить с нашим текущим капиталом.
  3. Для каждой возможности выбрать проект (до k раз) добавить в максимальную кучу те проекты, которые мы можем себе позволить, и из кучи выбрать тот, который приносит максимальную прибыль.
  4. Добавьте прибыль выбранного проекта к нашему общему капиталу.
  5. Повторяйте шаги 3 и 4 до тех пор, пока мы не выберем k проектов или больше проектов не будет.

Код решения с построчным объяснением:

    # Pair each project's capital requirement with its profit
    projects = sorted(zip(capital, profits))

    # Max heap to store profitable projects we can afford
    heap = []
    
    # Index for the sorted projects array
    i = 0
    
    # We can choose up to 'k' projects
    for _ in range(k):
        # Add projects we can afford to the max heap
        while i < n and projects[i][0] <= w:
            heapq.heappush(heap, -projects[i][1])
            i += 1
        
        # If the heap is empty, we can't afford any more projects
        if not heap:
            return w
        
        # Choose the most profitable project we can afford
        # and add its profits to our capital
        w -= heapq.heappop(heap)
    
    # Our capital after completing the projects
    return w

Только код решения:

    projects = sorted(zip(capital, profits))
    heap = []
    i = 0
    
    for _ in range(k):
        while i < n and projects[i][0] <= w:
            heapq.heappush(heap, -projects[i][1])
            i += 1
        
        if not heap:
            return w
        
        w -= heapq.heappop(heap)
    
    return w

Анализ сложности:

Сложность времени: O(n log n + k log n), где n — количество проектов, а k — максимальное количество проектов, которые можно выбрать. Сортировка проектов занимает O(n log n) времени, а операции с кучей внутри цикла занимают O(k log n) времени на всех итерациях.

Сложность пространства: O(n), где n — количество проектов. Это позволяет хранить проекты в отсортированном виде и отслеживать наиболее прибыльные из них в максимальной куче.