Проблем враћања кусура

Проблем враћања кусура поставља следеће питање: како се од понуђених апоена може направити задата сума новца, а да се притом искористи најмањи могући број новчића? Овај проблем је налик проблему ранца и има већу примену од пуког враћања кусура.

**Кованице српских динара припадају 1-2-5 серији**
1 динар	2 динар	5 динар

Зграда НБС	Манастир Грачаница	Манастир Крушедол
10 динара	20 динара

Манастир Студеница	Храм Светог Саве на Врачару

Математичка дефиниција

Вредности новчича могу бити представљене скупом од н различитих позитивних целих бројева уређених у растућем поретку као $\{w_{1},w_{2},\cdots w_{n}\}$ . Проблем захтева следеће: дата је сума $W$ , која је такође позитиван цео број и треба пронаћи скуп не-негативних целих бројева $\{x_{1},x_{2},\cdots x_{n}\}$ . Број $x_{j}$ представља колико је пута новчић са вредношћу $w_{j}$ употребљен, што минимизује укупан број новчића:

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

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

Методе решавања

Динамичко програмирање

Класична стратегија динамичког програмирања ради тако што се решење гради навише проналажењем комбнација свих мањих вредности које заједно дају вредност текућег прага. Тако, на сваком прагу, сви претходни прагови су већ потенцијално разматрани до циљне тежине $W$ . Из тог разлога, овај динамички приступ може бити барем квадратне сложености.

Најповољнија подструктура

Можемо искористити стратегију динамичког програмирања да реши овај проблем јер приказује најповољнију подструктуру.

Доказ

Претпоставимо да је $S$ најповољније решење за прављење скупа од н новчића. Онда је $S'=S-c$ , $c\in S$ , најповољније решење за потпроблем прављења скупа од $n$ – $c$ новчића. Сада, претпоставимо да $S'$ није најповољније решење за овај потпроблем, онда мора постојати неко повољније решење које означавамо са $X\neq S'$ . Пошто је $X$ најповољније решење, мора садржати мањи број новчића од решења $S'$ . Ако комбинујемо $X$ са $c$ , добијамо најповољније решење за $n$ новчића, али ово је у контрадикцији са нашом полазном претпоставком да је $S$ најповољније решење за овај проблем.

Имплементација

Следећеи код је имплементација динамичког решења у програмском језику Пајтон 3, где се користи матрица за праћење најповољнијих решења за потпроблеме. Као крајњи резултат добијамо минималан износ новчића. Ако желите да добијете скуп новчића за најповољније решење, можете користити и додатну матрицу.

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]

Ово је имплементација у програмском језику C сложености $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;
}

Динамичко програмирање и стабло вероватноће сложености

Ово стабло^[1] се може користити за ефикаснији динамички приступ. Стабло спаја парове новчића како би произвело све своте које могу бити направљене од парова новчића (без присутног иједног новчића из пара, само први новчић присутан, само други, оба присутна). Стабло затим спаја парове резултата спајања на исти начин. Овај процес се понавља све док последња два резултата спајања не буду спојена у један, што доводи до балансираног бинарног стабла са $Wlog(W)$ таквих операција спајања.

Штавише, дискретизовањем вредности новчића, свака од ових операција спајања може бити изведена путем конволуције, што се често може ефикасније извести Фуријеовим Брзим Трансформацијама (ФФТ). На овај начин, стабло се може користити како би се постигло решење сложености мање од квадратне: свака конволуција се може извести у $log(n)$ корака, а почетне операције спајања (којих уједно и има више) захтевају мање од н корака, док оне касније операције спајања захтевају $n$ .

Стабло базирано на методу динамичког програмирања такође ефикасно решава и генерализацију вероватноће проблема враћања кусура, где је сума $W$ неодређена, прави од тога дискретну поделу, где је вредности сваког од новчића исто тако дозвољено да буде неодређена (на пример, када се разматра курс) и где различити новчићи могу бити коришћени са одређеном учестаношћу.

Линеарно програмирање

Линеарно програмирање у ком су све непознате варијабле цели бројеви је често брз начин да се реши оваква врста проблема, али није сигурно у којем времену и овакво решење може бити споро у неким случајевима.

Похлепни метод

У САД и многим другим држававама постоји такозвани канонички систем новчића и за такве системе је згодно користити похлепан алгоритам. Овај приступ подразумева бирање највећег апоена који није већи од суме коју је потребно направити I то је често оптимално решење^[2]. Ово није случај у произвољним системима новчића: ако су вредности апоена новчића 1, 3 I 4, и потребно је направити 6, онда похлепан алгоритам бира решење са 3 новчића (4, 1, 1) уместо са 2 (3, 3).

Слични проблеми

Проблем оптималног апоена^[3] је проблем за људе који моделују сасвим нове вредности: које апоене треба изабрати у циљу смањења просечне сложености прављења кусура (нпр. који је просечан број новчића потребан да би се направио кусур?). Варијанта овог проблема претпоставља да ће људи при прављењу кусура користити минималан број новчића (од доступних апоена). Друга варијанта претпоставља да ће људи користити похлепан алгоритам, чак и онда када то захтева више од минималног броја новчића. Много тренутних валута користи 1-2-5 серије, али неки други скупови апоена би захтевали мање апоена или мањи просечан број новчића за прављење кусура или обоје.

Проблем враћања кусура се може применити при израчунавању начина на које играч може да направи такозвани нине-дарт-финисх у игри пикадо.

Види још

Референце

^ Серанг 2014: Серанг, О. (2012). „Тхе Пробабилистиц Цонволутион Трее: Еффициент Еxацт Баyесиан Инференце фор Фастер ЛЦ-МС/МС Протеин Инференце”. ПЛОС ОНЕ. 7 (3): е91507. дои:10.1371/јоурнал.поне.0091507.
^ Цаи, Xуан (2009). „Цаноницал Цоин Сyстемс фор ЦХАНГЕ-МАКИНГ Проблемс”. Процеедингс оф тхе Нинтх Интернатионал Цонференце он Хyбрид Интеллигент Сyстемс. 1: 499—504. дои:10.1109/ХИС.2009.103.
^ Схаллит, Ј. „Wхат тхис цоунтрy неедс ис ан 18ц пиеце” (ПДФ). Матхематицал Интеллигенцер. 25 (2): 20—23. дои:10.1007/БФ02984830.

Литература

Цаи, X. (2009). „Цаноницал Цоин Сyстемс фор Цханге-Макинг Проблемс”. Процеедингс оф тхе Нинтх Интернатионал Цонференце он Хyбрид Интеллигент Сyстемс: 499—504. арXив:0809.0400  . дои:10.1109/ХИС.2009.103.
M. Адамасзек, А. Ниеwиароwска (2010). „Цомбинаторицс оф тхе цханге-макинг проблем”. Еуропеан Јоурнал оф Цомбинаторицс. 31 (1): 47—63. арXив:0801.0120  . дои:10.1016/ј.ејц.2009.05.002.

[Serang-1] Серанг 2014: Серанг, О. (2012). „Тхе Пробабилистиц Цонволутион Трее: Еффициент Еxацт Баyесиан Инференце фор Фастер ЛЦ-МС/МС Протеин Инференце”. ПЛОС ОНЕ. 7 (3): е91507. дои:10.1371/јоурнал.поне.0091507.

[2] Цаи, Xуан (2009). „Цаноницал Цоин Сyстемс фор ЦХАНГЕ-МАКИНГ Проблемс”. Процеедингс оф тхе Нинтх Интернатионал Цонференце он Хyбрид Интеллигент Сyстемс. 1: 499—504. дои:10.1109/ХИС.2009.103.

[3] Схаллит, Ј. „Wхат тхис цоунтрy неедс ис ан 18ц пиеце” (ПДФ). Матхематицал Интеллигенцер. 25 (2): 20—23. дои:10.1007/БФ02984830.

[1]

[2]

[3]