Проблема с напоминанием - проблема дома грабителя - PullRequest
Новая
       53

Проблема с напоминанием - проблема дома грабителя

0 голосов
/ 20 января 2019

У меня есть рекурсивное решение, которое работает, но оказывается, что многие подзадачи пересчитываются. Мне нужна помощь с MEMOIZATION.

Итак, вот формулировка проблемы:

Вы профессиональный грабитель, планирующий грабить дома по улице. Каждый дом имеет определенную сумму денег, единственное ограничение мешает вам ограбить каждый из них, что соседние дома имеют система безопасности подключена и она автоматически свяжется с полицией если два соседних дома были взломаны в одну и ту же ночь.

Приведен список неотрицательных целых чисел, представляющих сумму денег определить максимальную сумму денег, которую вы можете ограбить сегодня без предупреждения полиции.

Примеры:

Ввод: [2,7,9,3,1] Ввод: 12 Пояснение: Роб-хаус 1 (деньги = 2), грабить дом 3 (деньги = 9) и грабить дом 5 (деньги = 1). Общая сумма, которую вы можете ограбить = 2 + 9 + 1 = 12.

Еще один:

Ввод: [1,2,3,1] Ввод: 4 Объяснение: Роб-хаус 1 (деньги = 1) и затем ограбить дом 3 (деньги = 3). Общая сумма, которую вы можете ограбить = 1 + 3 = 4.

и еще один

Ввод: [2, 1, 1, 2] Ввод: 4 Объяснение: Роб Хаус 1 (деньги = 2) и затем ограбить дом 4 (деньги = 2). Общая сумма, которую вы можете ограбить = 2 + 2 = 4.

Теперь, как я уже сказал, у меня есть идеально работающее рекурсивное решение: когда я создаю рекурсивное решение. Я не думаю слишком много. Я просто пытаюсь понять, что меньшие подзадачи.

option_1: я добавляю значение в свой текущий index и перехожу к index + 2

option_2: я не добавляю значение в свой текущий index, и я ищу, начиная с index + 1 Максимальная сумма денег = max(option_1, option_2)

money = [1, 2, 1, 1] #Amounts that can be looted


def helper(value, index):

    if index >= len(money):

        return value

    else:
        option1 = value + money[index]
        new_index1 = index + 2

        option2 = value
        new_index2 = index + 1

        return max(helper(option1, new_index1), helper(option2, new_index2))



helper(0, 0) #Starting of at value = 0 and index = 0

Это отлично работает .. и возвращает правильное значение 3.

Затем я попробую свои силы в MEMOIZING. 

money = [1, 2, 1, 1]

max_dict = {}
def helper(value, index):

    if index in max_dict:
        return max_dict[index]

    elif index >= len(l1):

        return value

    else:
        option1 = value + money[index]
        new_index1 = index + 2

        option2 = value
        new_index2 = index + 1

        max_dict[index] = max(helper(option1, new_index1), helper(option2, new_index2))

        return max_dict[index]


helper(0, 0)

У меня просто есть словарь под названием max_dict, в котором хранится значение, и каждый рекурсивный вызов проверяет, существует ли значение, а затем соответствующим образом захватывает его и распечатывает.

Но я получаю неправильное решение для этого как 2 вместо 3. Я пошел к pythontutor.com и напечатал свое решение, но я не могу получить дерево рекурсии и где оно терпит неудачу ..

Может ли кто-нибудь дать мне правильную реализацию памятки при сохранении общей структуры? Другими словами, я не хочу, чтобы определение рекурсивной функции изменилось

Ответы [ 2 ]

0 голосов
/ 20 января 2019

Ваш подход к запоминанию не будет работать, потому что когда вы достигнете некоторого индекса i, если вы уже вычислили какой-то результат для i, ваш алгоритм не учитывает тот факт, что может быть лучше результат возможен при ограблении более оптимального набора домов в левой части массива.

Решение этой дилеммы состоит в том, чтобы избежать прохождения бегущей строки value (деньги, которые вы ограбили) вниз черезрекурсивные звонки от родителей к детям.Идея состоит в том, чтобы вычислить результаты подзадачи без какого-либо ввода от узлов-предков, а затем создать более крупные решения из меньших по пути к стеку вызовов.

Запоминание индекса i будет тогда работать, потому что данный индекс i всегда будет иметь уникальный набор подзадач, решения которых не будут искажены при выборе из предков в левой части массива.Это сохраняет оптимальную подструктуру, необходимую для работы DP.

Кроме того, я рекомендую избегать глобальных переменных в пользу передачи ваших данных непосредственно в функцию. 

def maximize_robberies(houses, memo, i=0):
    if i in memo:
        return memo[i]
    elif i >= len(houses):
        return 0

    memo[i] = max(
        houses[i] + maximize_robberies(houses, memo, i + 2),
        maximize_robberies(houses, memo, i + 1)
    )
    return memo[i]


print(maximize_robberies([1, 2, 1, 1], {}))

Попробуйте это!

0 голосов
/ 20 января 2019

helper можно вызвать с другим параметром value для того же index. Таким образом, value должен быть удален (вычтен из сохраненного max_dict). Один из способов сделать это - добавить value непосредственно перед возвратом, а не раньше: 

money = [2, 1, 1, 2]

max_dict = {}
def helper(value, index):

    if index in max_dict:
        return value + max_dict[index]

    elif index >= len(money):

        return value

    else:
        option1 = money[index]
        new_index1 = index + 2

        option2 = 0
        new_index2 = index + 1

        max_dict[index] = max(helper(option1, new_index1), helper(option2, new_index2))

        return value + max_dict[index]


helper(0, 0)

Более подробное объяснение того, что происходит, дается ответом @ ggorlen

...