Problem wydawania reszty
Lekcja 8 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
Problem wydawania reszty to klasyczny problem programowania dynamicznego. Mając zestaw monet o różnych nominałach i określoną sumę pieniędzy, należy znaleźć minimalną liczbę monet potrzebnych do uzyskania tej sumy.
Załóżmy na przykład, że mamy monety o nominałach [1, 5, 10] i chcemy uzyskać sumę 15. Minimalna liczba potrzebnych monet wynosi 2 (moneta o nominale 10 i moneta o nominale 5).
Aby rozwiązać ten problem za pomocą programowania dynamicznego, możemy utworzyć tabelę, w której wiersze będą reprezentować nominały monet, a kolumny — kwoty od 0 do podanej sumy. Następnie wypełniamy tabelę od dołu do góry, obliczając minimalną liczbę monet potrzebnych do uzyskania każdej kwoty za pomocą monet o poszczególnych nominałach.
Wyzwanie
ŚredniNapisz program, który przyjmuje dwa wejścia: listę nominałów monet i kwotę docelową, a następnie zwraca minimalną liczbę monet potrzebnych do uzyskania kwoty docelowej.
Na przykład dla nominałów [1, 5, 10] i kwoty docelowej 15 wynikiem powinno być 2.
Spróbuj swoich sił
def min_coins(coins, target):
# Wpisz kod tutajWszystkie 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