Pruning
Lektion 11 von 15 im Kurs Dynamische Programmierung 101 von Coddy.
Pruning ist eine Technik, die verwendet wird, um die Anzahl der Berechnungen eines dynamischen Programmieralgorithmus zu reduzieren, indem unnötige Berechnungen vermieden werden. Dies geschieht durch das Eliminieren bestimmter Zweige des rekursiven Baums, die nicht zu einer besseren Lösung führen als der bisher gefundenen besten Lösung. Pruning kann sowohl in Top-Down- als auch in Bottom-Up-Algorithmen der dynamischen Programmierung eingesetzt werden.
Aufgabe
ExperteIn dieser Herausforderung erhalten Sie eine Matrix aus Ganzzahlen und einen Zielwert. Ihre Aufgabe ist es, aus jeder Zeile der Matrix eine Ganzzahl so auszuwählen, dass die absolute Differenz zwischen dem Zielwert und der Summe der ausgewählten Ganzzahlen minimiert wird. Sie müssen dann den Wert dieser minimalen absoluten Differenz zurückgeben.
Probier es selbst
def minimize_difference(mat, target):
# Code hier schreibenAlle Lektionen in Dynamische Programmierung 101
3Algorithmen der dynamischen Programmierung
Längste gemeinsame TeilsequenzRucksackproblemWechselgeldproblemEdit-Distanz