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.
1 dinar | 2 dinar | 5 dinar |
---|---|---|
10 dinara | 20 dinara | |
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 . Problem zahteva sledeće: data je suma , koja je takođe pozitivan ceo broj i treba pronaći skup ne-negativnih celih brojeva . Broj predstavlja koliko je puta novčić sa vrednošću upotrebljen, što minimizuje ukupan broj novčića:
.
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 . 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 najpovoljnije rešenje za pravljenje skupa od n novčića. Onda je , , najpovoljnije rešenje za potproblem pravljenja skupa od – novčića. Sada, pretpostavimo da nije najpovoljnije rešenje za ovaj potproblem, onda mora postojati neko povoljnije rešenje koje označavamo sa . Pošto je najpovoljnije rešenje, mora sadržati manji broj novčića od rešenja . Ako kombinujemo sa , dobijamo najpovoljnije rešenje za novčića, ali ovo je u kontradikciji sa našom polaznom pretpostavkom da je 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 .
#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[1] 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 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 koraka, a početne operacije spajanja (kojih ujedno i ima više) zahtevaju manje od n koraka, dok one kasnije operacije spajanja zahtevaju .
Stablo bazirano na metodu dinamičkog programiranja takođe efikasno rešava i generalizaciju verovatnoće problema vraćanja kusura, gde je suma 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[2]. 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[3] 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š
уредиReference
уреди- ^ Serang 2014 : Serang, O. (2012). „The Probabilistic Convolution Tree: Efficient Exact Bayesian Inference for Faster LC-MS/MS Protein Inference”. PLOS ONE. 7 (3): e91507. doi:10.1371/journal.pone.0091507.
- ^ Cai, Xuan (2009). „Canonical Coin Systems for CHANGE-MAKING Problems”. Proceedings of the Ninth International Conference on Hybrid Intelligent Systems. 1: 499—504. doi:10.1109/HIS.2009.103.
- ^ Shallit, J. „What this country needs is an 18c piece” (PDF). Mathematical Intelligencer. 25 (2): 20—23. doi:10.1007/BF02984830.
Литература
уреди- 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.