J'ai une solution récursive qui fonctionne, mais il s'avère que beaucoup de sous-problèmes sont recalculés. J'ai besoin d'aide pour la MÉMOISATION.
Voici donc l'énoncé du problème:
Vous êtes un voleur professionnel qui envisage de cambrioler des maisons le long d'une rue. Chaque maison a une certaine somme d'argent en réserve, la seule contrainte vous empêchant de voler chacun d'eux est que les maisons adjacentes ont système de sécurité connecté et il contactera automatiquement la police si deux maisons adjacentes ont été cambriolées la même nuit.
Étant donné une liste d'entiers non négatifs représentant le montant d'argent de chaque maison, déterminez le montant maximum d'argent que vous pouvez voler ce soir sans alerter la police.
Exemples:
Entrée:
[2,7,9,3,1]Sortie:12Explication: Rob house 1 (money = 2), voler la maison 3 (argent = 9) et voler la maison 5 (argent = 1). Montant total que vous pouvez voler =2 + 9 + 1 = 12.
Un autre:
Entrée:
[1,2,3,1]Sortie:4Explication: Rob house 1 (money = 1) et puis voler la maison 3 (argent = 3). Montant total que vous pouvez voler =1 + 3 = 4.
Et un autre
Entrée:
[2, 1, 1, 2]Sortie:4Explication: Rob house 1 (money = 2) et puis voler la maison 4 (argent = 2). Montant total que vous pouvez voler =2 + 2 = 4.
Maintenant, comme je l'ai dit, j'ai une solution récursive parfaitement fonctionnelle: quand je construis une solution récursive. Je ne pense pas trop. J'essaie juste de comprendre quels sont les petits sous-problèmes.
option_1 : j'ajoute la valeur dans mon index actuel, et je vais à index + 2
option_2 : Je n'ajoute pas la valeur dans mon index actuel, et je recherche à partir de index + 1
Montant maximum = max (option_1, option_2)
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)
Cela fonctionne parfaitement .. et renvoie la valeur correcte 3 code >.
Je m'essaye ensuite à la MÉMOISATION.
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
J'ai simplement un dictionnaire appelé max_dict qui STORE la valeur, et chaque appel récursif vérifie si la valeur existe déjà, puis la saisit en conséquence et l'imprime ..
Mais j'obtiens la mauvaise solution pour cela comme 2 au lieu de 3 . Je suis allé sur pythontutor.com et j'ai tapé ma solution, mais je n'arrive pas à trouver l'arborescence de récursivité et où elle échoue.
Quelqu'un pourrait-il me donner une mise en œuvre correcte de la mémorisation tout en gardant la même structure globale? En d'autres termes, je ne veux pas que la définition de la fonction récursive change
3 Réponses :
Le helper peut être appelé avec un paramètre de valeur différent pour le même index . La valeur doit donc être supprimée (soustraite du max_dict stocké). Une façon de faire est d'ajouter une valeur juste avant de retourner, pas plus tôt:
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)
Une explication plus détaillée de ce qui se passe est donnée par la réponse de @ ggorlen
Votre approche de la mémorisation ne fonctionnera pas car lorsque vous atteignez un index i , si vous avez déjà calculé un résultat pour i , votre algorithme ne prend pas en compte le fait qu'il pourrait y avoir un meilleur résultat disponible en volant un ensemble plus optimal de maisons dans la partie gauche du tableau.
La solution à ce dilemme est d'éviter de passer la valeur courante (l'argent que vous avez volé) vers le bas grâce aux appels récursifs des parents aux enfants. L'idée est de calculer les résultats des sous-problèmes sans aucune entrée à partir des nœuds ancêtres, puis de construire les solutions les plus grandes à partir des plus petites en remontant la pile d'appels.
index i fonctionnera alors car un index donné i aura toujours un ensemble unique de sous-problèmes dont les solutions ne seront pas corrompues par les choix des ancêtres dans la partie gauche du tableau. Cela préserve la sous-structure optimale nécessaire au fonctionnement de DP.
De plus, je recommande d'éviter les variables globales en faveur du passage de vos données directement dans la fonction.
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], {}))
Essayez-le!
Merci ggorlen, je vais devoir accepter la réponse de Michael parce qu'il n'a pas changé la structure générale. J'apprécie l'explication que vous avez donnée.
Il n'y a malheureusement PAS assez de façons de dire merci. :)
J'ai résolu ce problème de programmation dynamique en utilisant la méthode ci-dessous. Et cela arrive dans le temps O (n). Essayez ceci.
class Solution:
# @param {integer[]} nums
# @return {integer}
def rob(self, nums):
n = len(nums)
if n==0:
return 0;
if n == 1:
return nums[0]
s = [0]*(n+1)
s[1] = nums[0]
s[2] = nums[1]
for i in range(3,n+1):
s[i] = (max(s[i-2],s[i-3]) + nums[i-1])
return max(s[n],s[n-1])
money = [2, 1, 1, 2]
sol = Solution()
print(sol.rob(money))
Merci! Mais j'ai eu la réponse il y a longtemps