Jednoduché dynamické programováníEdit
Klasická strategie dynamického programování pracuje směrem nahoru tak, že najde kombinace všech menších hodnot, jejichž součet by se rovnal aktuálnímu prahu. Při každé prahové hodnotě se tedy potenciálně uvažují všechny předchozí prahové hodnoty, aby bylo možné pracovat směrem nahoru k cílové částce W. Z tohoto důvodu tento přístup dynamického programování vyžaduje počet kroků, který je O(nW), kde n je počet druhů mincí.
ImplementaceUpravit
Následuje implementace dynamického programování (s Pythonem 3), která používá matici pro sledování optimálních řešení dílčích problémů a vrací minimální počet mincí nebo „nekonečno“, pokud s danými mincemi nelze provést změnu. K získání množiny mincí pro optimální řešení lze použít druhou matici.
def _get_change_making_matrix(set_of_coins, r: int): m = for _ in range(len(set_of_coins) + 1)] for i in range(1, r + 1): m = float('inf') # By default there is no way of making change return mdef change_making(coins, n: int): """This function assumes that all coins are available infinitely. n is the number to obtain with the fewest coins. coins is a list or tuple with the available denominations. """ m = _get_change_making_matrix(coins, n) for c in range(1, len(coins) + 1): for r in range(1, n + 1): # Just use the coin coins. if coins == r: m = 1 # coins cannot be included. # Use the previous solution for making r, # excluding coins. elif coins > r: m = m # coins can be used. # Decide which one of the following solutions is the best: # 1. Using the previous solution for making r (without using coins). # 2. Using the previous solution for making r - coins (without # using coins) plus this 1 extra coin. else: m = min(m, 1 + m]) return m
Dynamické programování s pravděpodobnostním konvolučním stromemUpravit
Jako efektivnější přístup k dynamickému programování lze použít také pravděpodobnostní konvoluční strom. Pravděpodobnostní konvoluční strom sloučí dvojice mincí tak, aby vznikly všechny částky, které mohou být vytvořeny danou dvojicí mincí (bez přítomnosti žádné mince, pouze s přítomností první mince, pouze s přítomností druhé mince a s přítomností obou mincí), a následně stejným způsobem sloučí dvojice těchto sloučených výsledků. Tento postup se opakuje, dokud nejsou poslední dvě kolekce výsledků sloučeny do jedné, což vede k vyváženému binárnímu stromu s W log(W) takových operací sloučení. Díky diskretizaci hodnot mincí lze navíc každou z těchto slučovacích operací provádět pomocí konvoluce, kterou lze často provádět efektivněji pomocí rychlé Fourierovy transformace (FFT). Tímto způsobem lze pomocí pravděpodobnostního konvolučního stromu dosáhnout řešení v subkvadratickém počtu kroků: každou konvoluci lze provést v n log(n) a počáteční (početnější) slučovací operace používají menší n, zatímco pozdější (méně početné) operace vyžadují n v řádu W.
Metoda dynamického programování založená na pravděpodobnostním konvolučním stromu také efektivně řeší pravděpodobnostní zobecnění problému směny, kde neurčitost nebo rozmazanost cílové částky W z ní činí diskrétní rozdělení, nikoli pevnou veličinu, kde hodnota každé mince může být rovněž rozmazaná (například při uvažování směnného kurzu) a kde různé mince mohou být používány s určitou četností.
Chamtivá metodaEdit
U takzvaných kanonických mincovních systémů, jaké se používají v USA a mnoha dalších zemích, povede k optimálnímu výsledku chamtivý algoritmus výběru největší nominální hodnoty mince, která není větší než zbývající částka, kterou je třeba vyrobit. To však neplatí pro libovolné mincové systémy. Pokud by například nominální hodnoty mincí byly 1, 3 a 4, pak pro výrobu 6 mincí by chamtivý algoritmus zvolil tři mince (4,1,1), zatímco optimálním řešením jsou dvě mince (3,3). V polynomiálním čase je možné otestovat, zda je soustava mincí kanonická (tj. zda chamtivý algoritmus řeší její problém rozměňování vždy optimálně)
.