Problem vraćanja kusura

Problem vraćanja kusura postavlja sledeće pitanje: kako se od ponuđenih apoena može napraviti zadata suma novca, a da se pritom iskoristi najmanji mogući broj novčića? Ovaj problem je nalik problemu ranca i ima veću primenu od pukog vraćanja kusura.

Коvanice srpskih dinara pripadaju 1-2-5 seriji

1 dinar	2 dinar	5 dinar
Zgrada NBS	Manastir Gračanica	Manastir Krušedol
10 dinara	20 dinara
Manastir Studenica	Hram Svetog Save nа Vračaru

Matematička definicija

Vrednosti novčiča mogu biti predstavljene skupom od n različitih pozitivnih celih brojeva uređenih u rastućem poretku kao $\{w_{1},w_{2},\cdots w_{n}\}$. Problem zahteva sledeće: data je suma $W$, koja je takođe pozitivan ceo broj i treba pronaći skup ne-negativnih celih brojeva $\{x_{1},x_{2},\cdots x_{n}\}$. Broj $x_{j}$ predstavlja koliko je puta novčić sa vrednošću $w_{j}$ upotrebljen, što minimizuje ukupan broj novčića:

$\sum _{j=1}^{n}x_{j}$

$\sum _{j=1}^{n}w_{j}x_{j}=W$.

Metode rešavanja

Dinamičko programiranje

Klasična strategija dinamičkog programiranja radi tako što se rešenje gradi naviše pronalaženjem kombnacija svih manjih vrednosti koje zajedno daju vrednost tekućeg praga. Tako, na svakom pragu, svi prethodni pragovi su već potencijalno razmatrani do ciljne težine $W$. Iz tog razloga, ovaj dinamički pristup može biti barem kvadratne složenosti.

Najpovoljnija podstruktura

Možemo iskoristiti strategiju dinamičkog programiranja da reši ovaj problem jer prikazuje najpovoljniju podstrukturu.

Dokaz

Pretpostavimo da je $S$ najpovoljnije rešenje za pravljenje skupa od n novčića. Onda je $S'=S-c$ , $c\in S$, najpovoljnije rešenje za potproblem pravljenja skupa od $n$ – $c$ novčića. Sada, pretpostavimo da $S'$ nije najpovoljnije rešenje za ovaj potproblem, onda mora postojati neko povoljnije rešenje koje označavamo sa $X\neq S'$. Pošto je $X$ najpovoljnije rešenje, mora sadržati manji broj novčića od rešenja $S'$. Ako kombinujemo $X$ sa $c$, dobijamo najpovoljnije rešenje za $n$ novčića, ali ovo je u kontradikciji sa našom polaznom pretpostavkom da je $S$ najpovoljnije rešenje za ovaj problem.

Implementacija

Sledećei kod je implementacija dinamičkog rešenja u programskom jeziku Pajton 3, gde se koristi matrica za praćenje najpovoljnijih rešenja za potprobleme. Kao krajnji rezultat dobijamo minimalan iznos novčića. Ako želite da dobijete skup novčića za najpovoljnije rešenje, možete koristiti i dodatnu matricu.

def _get_change_making_matrix(set_of_coins, r):
    m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]

    for i in range(r + 1):
        m[0][i] = i

    return m

def change_making(coins, n):
    """Funkcija pretpostavlja da su svi novčiči dostupni neograničen broj puta.

    n je broj koji je potrebno dobiti sa najmanjim brojem novčića

    coins je lista dostupnih apoena."""

    m = _get_change_making_matrix(coins, n)

    for c in range(1, len(coins) + 1):

        for r in range(1, n + 1):

            # Koristi samo novčić coins[c - 1]
            if coins[c - 1] == r:
                m[c][r] = 1

            # coins[c - 1] se ne može uključiti
            # Koristimo prethodno rešenje za pravljenje r,
            # sključujući coins[c - 1].
            elif coins[c - 1] > r:
                m[c][r] = m[c - 1][r]

            # Možemo koristiti coins[c - 1].
            # Moramo odlučiti koje od navedenih rešenja je najbolje:
            # 1. korišćenje prethodnog rešenja da bi se napravilo r (bez korišćenja coins[c - 1])
            # 2. korišćenje prethodnog rešenja da bi se napravilo r - coins[c - 1] (bez korišćenja coins[c - 1])
            # plus jedan dodatni novčić
            else:
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])

    return m[-1][-1]

Ovo je implementacija u programskom jeziku C složenosti $O(mn)$.

#include<stdio.h>
 
int count( int S[], int m, int n )
{
    int i, j, x, y;
 
    // Treba nam n+1 red jer se tabela gradi odozdo prema nagore
    // Bazni slučaj je 0 vrednost kada je n = 0
    int table[n+1][m];
    
    // Bazni slučaj
    for (i=0; i<m; i++)
        table[0][i] = 1;
 
    // Popunjavanje ostatka tabele
    for (i = 1; i < n+1; i++)
    {
        for (j = 0; j < m; j++)
        {
            // Broj rešenja uključujući S[j]
            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
 
            // Broj rešenja bez S[j]
            y = (j >= 1)? table[i][j-1]: 0;
 
            // Ukupan broj rešenja
            table[i][j] = x + y;
        }
    }
    return table[n][m-1];
}
 
// Testiranje funkcije
int main()
{
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    printf(" %d ", count(arr, m, n));
    return 0;
}

Dinamičko programiranje i stablo verovatnoće složenosti

Ovo stablo se može koristiti za efikasniji dinamički pristup. Stablo spaja parove novčića kako bi proizvelo sve svote koje mogu biti napravljene od parova novčića (bez prisutnog ijednog novčića iz para, samo prvi novčić prisutan, samo drugi, oba prisutna). Stablo zatim spaja parove rezultata spajanja na isti način. Ovaj proces se ponavlja sve dok poslednja dva rezultata spajanja ne budu spojena u jedan, što dovodi do balansiranog binarnog stabla sa $Wlog(W)$ takvih operacija spajanja.

Štaviše, diskretizovanjem vrednosti novčića, svaka od ovih operacija spajanja može biti izvedena putem konvolucije, što se često može efikasnije izvesti Furijeovim Brzim Transformacijama (FFT). Na ovaj način, stablo se može koristiti kako bi se postiglo rešenje složenosti manje od kvadratne: svaka konvolucija se može izvesti u $log(n)$ koraka, a početne operacije spajanja (kojih ujedno i ima više) zahtevaju manje od n koraka, dok one kasnije operacije spajanja zahtevaju $n$.

Stablo bazirano na metodu dinamičkog programiranja takođe efikasno rešava i generalizaciju verovatnoće problema vraćanja kusura, gde je suma $W$ neodređena, pravi od toga diskretnu podelu, gde je vrednosti svakog od novčića isto tako dozvoljeno da bude neodređena (na primer, kada se razmatra kurs) i gde različiti novčići mogu biti korišćeni sa određenom učestanošću.

Linearno programiranje

Linearno programiranje u kom su sve nepoznate varijable celi brojevi je često brz način da se reši ovakva vrsta problema, ali nije sigurno u kojem vremenu i ovakvo rešenje može biti sporo u nekim slučajevima.

Pohlepni metod

U SAD i mnogim drugim državavama postoji takozvani kanonički sistem novčića i za takve sisteme je zgodno koristiti pohlepan algoritam. Ovaj pristup podrazumeva biranje najvećeg apoena koji nije veći od sume koju je potrebno napraviti I to je često optimalno rešenje. Ovo nije slučaj u proizvoljnim sistemima novčića: ako su vrednosti apoena novčića 1, 3 I 4, i potrebno je napraviti 6, onda pohlepan algoritam bira rešenje sa 3 novčića (4, 1, 1) umesto sa 2 (3, 3).

Slični problemi

Problem optimalnog apoena je problem za ljude koji modeluju sasvim nove vrednosti: koje apoene treba izabrati u cilju smanjenja prosečne složenosti pravljenja kusura (npr. koji je prosečan broj novčića potreban da bi se napravio kusur?). Varijanta ovog problema pretpostavlja da će ljudi pri pravljenju kusura koristiti minimalan broj novčića (od dostupnih apoena). Druga varijanta pretpostavlja da će ljudi koristiti pohlepan algoritam, čak i onda kada to zahteva više od minimalnog broja novčića. Mnogo trenutnih valuta koristi 1-2-5 serije, ali neki drugi skupovi apoena bi zahtevali manje apoena ili manji prosečan broj novčića za pravljenje kusura ili oboje.

Problem vraćanja kusura se može primeniti pri izračunavanju načina na koje igrač može da napravi takozvani nine-dart-finish u igri pikado.

Vidi još

• Dinamičko programiranje
• Pohlepni algoritam

Литература

• Cai, X. (2009). „Canonical Coin Systems for Change-Making Problems”. Proceedings of the Ninth International Conference on Hybrid Intelligent Systems: 499—504. arXiv:0809.0400 . doi:10.1109/HIS.2009.103. 
• M. Adamaszek, A. Niewiarowska (2010). „Combinatorics of the change-making problem”. European Journal of Combinatorics. 31 (1): 47—63. arXiv:0801.0120 . doi:10.1016/j.ejc.2009.05.002.