Egyszerű dinamikus programozásSzerkesztés
A klasszikus dinamikus programozási stratégia úgy dolgozik felfelé, hogy megkeresi az összes olyan kisebb érték kombinációját, amelyek összege elérné az aktuális küszöbértéket. Így minden egyes küszöbértéknél potenciálisan minden korábbi küszöbértéket figyelembe veszünk, hogy felfelé dolgozzunk a célösszegig W. Emiatt ez a dinamikus programozási megközelítés O(nW) számú lépést igényel, ahol n az érmék típusainak száma.
ImplementációSzerkesztés
A következő egy dinamikus programozási implementáció (Python 3-mal), amely egy mátrixot használ a részproblémák optimális megoldásainak nyomon követésére, és visszaadja a minimális érmeszámot, vagy “Végtelen”, ha a megadott érmékkel nem lehet váltani. Egy második mátrix segítségével megkaphatjuk az optimális megoldáshoz tartozó érmék halmazát.
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
Dinamikus programozás a valószínűségi konvolúciós fávalSzerkesztés
A valószínűségi konvolúciós fa egy hatékonyabb dinamikus programozási megközelítésként is használható. A valószínűségi konvolúciós fa összevonja az érmepárokat, hogy az összes olyan összeget előállítsa, amelyet az adott érmepár létrehozhat (egyik érme jelenléte, csak az első érme jelenléte, csak a második érme jelenléte és mindkét érme jelenléte esetén), majd ezt követően ugyanilyen módon összevonja ezen összevont eredmények párjait. Ez a folyamat addig ismétlődik, amíg az utolsó két kimenetelgyűjteményt egybe nem olvasztjuk, ami egy kiegyensúlyozott bináris fához vezet, W log(W) ilyen egyesítési művelettel. Továbbá az érmeértékek diszkretizálásával az egyesítési műveletek mindegyike elvégezhető konvolúcióval, ami gyakran hatékonyabban elvégezhető a gyors Fourier-transzformációval (FFT). Ily módon a valószínűségi konvolúciós fa segítségével szubkvadratikus számú lépésben érhető el a megoldás: minden egyes konvolúció n log(n) alatt végezhető el, és a kezdeti (nagyobb számú) egyesítési műveletekhez kisebb n, míg a későbbi (kisebb számú) műveletekhez W nagyságrendű n szükséges.
A valószínűségi konvolúciós fa alapú dinamikus programozási módszer hatékonyan megoldja a pénzváltási probléma valószínűségi általánosítását is, ahol a W célösszeg bizonytalansága vagy homályossága miatt a célösszeg nem egy fix mennyiség, hanem diszkrét eloszlás, ahol az egyes érmék értéke szintén megengedett, hogy homályos legyen (például ha egy árfolyamot veszünk figyelembe), és ahol különböző érmék meghatározott gyakorisággal használhatók.
Kapzsi módszerSzerkesztés
Az úgynevezett kanonikus érmés rendszerek esetében, mint amilyeneket az Egyesült Államokban és számos más országban használnak, a legnagyobb címletű érme kiválasztásának kapzsi algoritmusa, amely nem nagyobb, mint a fennmaradó összeg, optimális eredményt ad. Ez azonban nem igaz a tetszőleges érmés rendszerek esetében. Ha például az érmék címlete 1, 3 és 4 lenne, akkor a 6 érme elkészítéséhez a mohó algoritmus három érmét választana (4,1,1), míg az optimális megoldás két érme (3,3). Az, hogy egy érmés rendszer kanonikus-e (azaz, hogy a mohó algoritmus mindig optimálisan oldja-e meg a pénzváltási feladatot), polinomiális idő alatt vizsgálható.