Kilka miesięcy temu znalazłem fragment kodu, który przygotowywałem do rozmowy kwalifikacyjnej.
Zgodnie z komentarzem, który miałem, próbował rozwiązać ten problem:
Biorąc pod uwagę wartość dolara w centach (np. 200 = 2 dolary, 1000 = 10 dolarów), znajdź wszystkie kombinacje monet, które składają się na wartość dolara. Dozwolone są tylko grosze (1 ¢), 5 centów (5 centów), dziesięciocentówki (10 centów) i ćwiartki (25 centów).
Na przykład, jeśli podano 100, odpowiedź powinna brzmieć:
4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies
etc.
Uważam, że można to rozwiązać w sposób iteracyjny i rekurencyjny. Moje rozwiązanie rekurencyjne jest dość błędne i zastanawiałem się, jak inni ludzie mogą rozwiązać ten problem. Trudną częścią tego problemu było zapewnienie jak największej wydajności.
algorithm
recursion
puzzle
coin-change
codingbear
źródło
źródło
code-golf
=> stackoverflow.com/questions/tagged/code-golfOdpowiedzi:
Zajrzałem do tego kiedyś dawno temu i możesz przeczytać o tym mój mały opis . Oto źródło Mathematica .
Korzystając z funkcji generujących, można uzyskać rozwiązanie problemu w postaci zamkniętej w stałym czasie. Książka Grahama, Knutha i Patashnika Concrete Mathematics jest książką poświęconą temu zagadnieniu i zawiera dość obszerne omówienie problemu. Zasadniczo definiujesz wielomian, w którym n- ty współczynnik jest liczbą sposobów dokonywania zmiany dla n dolarów.
Strony 4-5 zapisu pokazują, jak można użyć Mathematica (lub innego wygodnego systemu algebry komputerowej) do obliczenia odpowiedzi za 10 ^ 10 ^ 6 dolarów w ciągu kilku sekund w trzech wierszach kodu.
(I to było wystarczająco dawno temu, że to kilka sekund na 75Mhz Pentium ...)
źródło
a
jako domenęf
alea = {1,5,10,25,50,100}
. Na liście monet powinno znajdować się 5 centów. W przeciwnym razie opis był fantastyczny, dzięki!Uwaga : pokazuje tylko liczbę sposobów.
Funkcja Scala:
źródło
n1 * coins(0) + n2 * coins(1) + ... + nN * coins(N-1) = money
. Więc dlamoney=0
icoins=List(1,2,5,10)
liczba kombinacji(n1, n2, n3, n4)
wynosi 1, a rozwiązaniem jest(0, 0, 0, 0)
.money == 0
alecoins.isEmpty
, to nie powinno się liczyć jako rozwiązanie. Dlatego też algo może być lepiej obsługiwane, jeślicoins.isEmpty || money < 0
warunek zostanie ck'd jako pierwszy.Wolałbym rozwiązanie rekurencyjne. Masz listę nominałów, jeśli najmniejszy może równo podzielić pozostałą kwotę waluty, powinno to działać dobrze.
Zasadniczo przechodzisz od największych do najmniejszych nominałów.
Rekurencyjnie,
Oto moja wersja Twojego problemu w Pythonie za 200 centów. Mam 1463 sposoby. Ta wersja wypisuje wszystkie kombinacje i ostateczną liczbę.
źródło
denominations
nie ma1
jako ostatniej wartości. Możesz dodać niewielką ilość kodu do najbardziej wewnętrznegoif
bloku, aby to naprawić (jak opisuję w mojej odpowiedzi na inne pytanie).Funkcja Scala:
źródło
Oto absolutnie prosty kod w C ++ rozwiązujący problem, który wymagał wyświetlenia wszystkich kombinacji.
Ale jestem dość zaintrygowany problemem podrzędnym polegającym na obliczaniu liczby kombinacji. Podejrzewam, że istnieje na to równanie w postaci zamkniętej.
źródło
Problem podrzędny jest typowym problemem programowania dynamicznego.
źródło
Kod wykorzystuje Javę do rozwiązania tego problemu i działa również ... Ta metoda może nie być dobrym pomysłem z powodu zbyt wielu pętli, ale jest to naprawdę prosta droga.
źródło
To jest naprawdę stare pytanie, ale wymyśliłem rozwiązanie rekurencyjne w Javie, które wydawało się mniejsze niż wszystkie inne, więc oto -
Ulepszenia:
źródło
Niech C (i, J) jest zbiorem kombinacji tworzenia i centów przy użyciu wartości ze zbioru J.
Możesz zdefiniować C jako:
(pierwszy (J) przyjmuje w deterministyczny sposób element zbioru)
Okazuje się, że jest to dość rekurencyjna funkcja ... i dość wydajna, jeśli używasz zapamiętywania;)
źródło
pół-hack, aby obejść problem unikalnej kombinacji - wymuś kolejność malejącą:
Będzie to działać wolno, ponieważ nie zostanie zapamiętane, ale masz pomysł.
źródło
źródło
To jest moja odpowiedź w Pythonie. Nie używa rekurencji:
Przykładowe dane wyjściowe
źródło
źródło
Obie: iteruj przez wszystkie nominały od najwyższego do najniższego, weź jeden z nominałów, odejmij od wymaganej sumy, a następnie powtórz na pozostałej części (ograniczając dostępne nominały, aby były równe lub niższe od bieżącej wartości iteracji).
źródło
Jeśli system walutowy na to pozwala, prosty chciwy algorytm który pobiera jak najwięcej monet, zaczynając od waluty o najwyższej wartości.
W przeciwnym razie, aby szybko znaleźć optymalne rozwiązanie, wymagane jest programowanie dynamiczne, ponieważ ten problem jest zasadniczo problemem plecaka .
Na przykład, jeśli system walutowy ma monety
{13, 8, 1}
:, chciwe rozwiązanie spowodowałoby zmianę za 24 as{13, 8, 1, 1, 1}
, ale prawdziwym optymalnym rozwiązaniem jest{8, 8, 8}
Edycja: Myślałem, że wprowadzamy zmiany optymalnie, a nie wymieniamy wszystkie sposoby wprowadzenia zmiany za dolara. W moim ostatnim wywiadzie zapytałem, jak wprowadzić zmiany, więc odskoczyłem do przodu, zanim skończyłem czytać pytanie.
źródło
Wiem, że to bardzo stare pytanie. Szukałem właściwej odpowiedzi i nie mogłem znaleźć niczego prostego i satysfakcjonującego. Zajęło mi to trochę czasu, ale udało mi się coś zapisać.
To jest rozwiązanie javascript i używa rekursji.
źródło
W języku programowania Scala zrobiłbym to tak:
źródło
Jest to prosty algorytm rekurencyjny, który pobiera rachunek, a następnie rekurencyjnie pobiera mniejszy rachunek, aż osiągnie sumę, następnie bierze kolejny weksel o tym samym nominale i ponownie powtarza. Zobacz przykładowe dane wyjściowe poniżej dla ilustracji.
Drukuje:
źródło
Duh, czuję się teraz głupio. Poniżej znajduje się zbyt skomplikowane rozwiązanie, które będę zachować, gdyż jest to rozwiązanie, mimo wszystko. Prostym rozwiązaniem byłoby to:
Oto inne rozwiązanie. To rozwiązanie opiera się na obserwacji, że każda moneta jest wielokrotnością pozostałych, więc można je przedstawić w ich kategoriach.
Na przykład za 37 monet:
źródło
Ten mój wpis na blogu rozwiązuje ten plecakowy problem z postaciami z komiksu XKCD . Prosta zmiana w
items
dyktandzie iexactcost
wartości przyniesie również wszystkie rozwiązania twojego problemu.Gdyby problem polegał na znalezieniu zmiany, która wymagała najmniejszego kosztu, to naiwny chciwy algorytm, który używałby tyle samo monety o najwyższej wartości, mógłby się nie powieść w przypadku niektórych kombinacji monet i kwoty docelowej. Na przykład, jeśli istnieją monety o wartości 1, 3 i 4; a docelowa kwota to 6, wtedy chciwy algorytm może zasugerować trzy monety o wartości 4, 1 i 1, gdy łatwo jest zauważyć, że można użyć dwóch monet o wartości 3.
źródło
źródło
Znalazłem ten zgrabny fragment kodu w książce „Python do analizy danych” autorstwa Ooreily. Używa leniwej implementacji i porównania int i przypuszczam, że można go zmodyfikować dla innych nominałów przy użyciu liczb dziesiętnych. Daj mi znać czy to ci pomogło!
źródło
To jest poprawa odpowiedzi Zihana. Wiele niepotrzebnych pętli pojawia się, gdy nominał wynosi zaledwie 1 cent.
Jest intuicyjny i nierekurencyjny.
źródło
Proste rozwiązanie Java:
źródło
źródło
Oto funkcja C #:
Użyj tego w ten sposób:
Drukuje:
źródło
Poniżej znajduje się program w Pythonie, który pozwala znaleźć wszystkie kombinacje pieniędzy. Jest to rozwiązanie do programowania dynamicznego z czasem zamówienia (n). Pieniądze to 1,5,10,25
Przechodzimy od rzędu pieniędzy 1 do rzędu pieniędzy 25 (4 rzędy). Wiersz pieniądz 1 zawiera liczbę, jeśli weźmiemy pod uwagę tylko pieniądze 1 przy obliczaniu liczby kombinacji. Pieniądze z wiersza 5 tworzą każdą kolumnę, biorąc liczbę w wierszu pieniądze r dla tych samych pieniędzy końcowych plus poprzednie 5 zliczeń w swoim własnym wierszu (bieżąca pozycja minus 5). Pieniądze z rzędu 10 wykorzystują pieniądze z rzędu 5, które zawierają zliczenia dla obu wartości 1,5 i dodają poprzednie 10 zliczeń (bieżąca pozycja minus 10). Pieniądze rzędu 25 wykorzystują pieniądze rzędu 10, które zawierają liczby dla pieniędzy rzędu 1,5,10 plus poprzednie 25 zliczeń.
Na przykład liczby [1] [12] = liczby [0] [12] + liczby [1] [7] (7 = 12-5), co daje 3 = 1 + 2; liczby [3] [12] = liczby [2] [12] + liczby [3] [9] (-13 = 12-25), co daje 4 = 0 + 4, ponieważ -13 to mniej niż 0.
źródło
Rozwiązanie Java
}
źródło
Poniższe rozwiązanie java, które wydrukuje również różne kombinacje. Łatwy do zrozumienia. Pomysł jest
za sumę 5
Rozwiązaniem jest
Jeśli pozostała suma w każdej pętli jest mniejsza niż nominał, tj. Jeśli pozostała suma 1 jest mniejsza niż 2, po prostu przerwij pętlę
Pełny kod poniżej
Proszę mnie poprawić w przypadku jakichkolwiek błędów
}
źródło
Oto rozwiązanie oparte na Pythonie, które wykorzystuje rekursję, a także zapamiętywanie, co powoduje złożoność O (mxn)
źródło