Przycinanie
Lekcja 11 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
Przycinanie to technika stosowana w celu zmniejszenia liczby obliczeń wymaganych przez algorytm programowania dynamicznego poprzez unikanie niepotrzebnych obliczeń. Polega ona na eliminowaniu niektórych gałęzi drzewa rekurencji, które nie doprowadzą do rozwiązania lepszego niż najlepsze dotychczas znalezione rozwiązanie. Przycinanie można stosować zarówno w algorytmach programowania dynamicznego od góry do dołu, jak i od dołu do góry.
Wyzwanie
EkspertW tym wyzwaniu otrzymujesz macierz liczb całkowitych i wartość docelową. Twoim zadaniem jest wybranie jednej liczby całkowitej z każdego wiersza macierzy tak, aby zminimalizować wartość bezwzględną różnicy między wartością docelową a sumą wybranych liczb całkowitych. Następnie musisz zwrócić wartość tej minimalnej różnicy bezwzględnej.
Spróbuj swoich sił
def minimize_difference(mat, target):
# Napisz tutaj kodWszystkie lekcje w sekcji Programowanie dynamiczne — podstawy
1Wprowadzenie do programowania dynamicznego
Czym jest programowanie dynamiczne?Dlaczego jest ważne?Zastosowania w różnych dziedzinach4Zaawansowane zagadnienia
Minimalna długość podtablicyPrzycinanieOptymalizacja pamięciMaskowanie bitów3Algorytmy programowania dynamicznego
Najdłuższy wspólny podciągProblem plecakowyProblem wydawania resztyOdległość edycyjnaPoćwicz samodzielnie: Kompilator Python online