Моя проблема заключается в следующем: у меня есть список миссий, каждая из которых занимает определенное количество времени и дает определенное количество очков, и время k, отводимое на их выполнение:
например: missions = [(14,3),(54,5),(5,4)] и time = 15
в этом примере у меня есть 3 миссии, и первая дает мне 14 очков и занимает 3 минуты. Всего у меня 15 минут. Каждая миссия представляет собой кортеж, первое значение которого представляет собой количество очков за эту миссию, а второе значение - количество минут, необходимых для выполнения этой миссии.
Я должен рекурсивно с помощью мемоизации найти максимальное количество очков, которое я могу получить за данный список миссий и за заданное время.
Я пытаюсь реализовать функцию под названием select (mission, time), которая будет работать рекурсивно и использовать функцию choose_mem (mission, time, mem, k) для достижения моей цели. функция select_mem должна получить «k» - количество миссий на выбор, а mem - пустой словарь mem, который будет содержать все проблемы, которые уже были решены ранее.
Это то, что я получил до сих пор, мне нужна помощь в реализации того, что требуется выше, я имею в виду использование словаря (который в настоящее время просто существует и все время пуст), а также тот факт, что мой ввод функции select_mem равен i,j,missions,d, и он должен быть choose_mem(missions, time, mem, k) где mem = d и k - количество миссий на выбор.
Если кто-нибудь может помочь мне настроить мой код, я был бы очень признателен.
mem = {}
def choose(missions, time):
j = time
result = []
for i in range(len(missions), 0, -1):
if choose_mem(missions, j, mem, i) != choose_mem(missions, j, mem, i-1):
j -= missions[i - 1][1]
return choose_mem(missions, time, mem, len(missions))
def choose_mem(missions, time, mem, k):
if k == 0: return 0
points, a = missions[k - 1]
if a > time:
return choose_mem(missions, time, mem, k-1)
else:
return max(choose_mem(missions, time, mem, k-1),
choose_mem(missions, time-a, mem, k-1) + points)
