Problem wydawania reszty

Oryginalny problem wydawania reszty to problem w którym musimy wydać daną kwotę minimalną ilością monet/ banknotów zakładając, że mamy nieskończoną ilość egzemplarzy monet/ banknotów każdego nominału. Są dwie wersje problemu: jedna w której mamy obliczyć tylko ile minimalnie musimy użyć monet i banknotów (ta wersja mnie nie interesuje) i druga w której oprócz tego musimy znaleźć kombinację monet i banknotów o minimalnej ilości która realizuje wypłatę.

Zakładając, że kwota do wydania to kwota, a nominały są zawarte w tablicy nominały, udało mi się stworzyć algorytm, będący lekką modyfikacją algorytmu z Wiki, który liczy rozwiązanie w czasie O(kwota * nominały.length) i używa, jak mi się wydaje po paru krótkich próbach, O(nominały.length) pamięci.
Algorytm jest tutaj: http://ideone.com/d6suB
Czy ktoś może potwierdzić, że ten algorytm rzeczywiście potrzebuje tylko O(nominały.length) pamięci? A może gdzieś na necie już jest rozwiązanie o interesującej mnie złożoności.
Algorytm wykorzystuje niemutowalne listy jednokierunkowe. Dzięki temu mogę utworzyć nową listę z listy o dowolnej długości i nowego elementu w czasie stałym i używając stałą ilość dodatkowej pamięci. Usuwaniem węzłów, które przestają być osiągalne zajmuje się oczywiście odśmiecacz wbudowany w maszynę wirtualną.

Docelowo chciałbym mieć bardziej rozbudowany algorytm. Otóz w moim problemie każdy nominał ma ograniczoną liczbę egzemplarzy. Ponadto chciałbym nadać priorytety konkretnym monetom i banknotom (nie konkretnym nominałom, a konkretnym monetom czy banknotom!). Priorytety są po to, żeby zapobiegać jak tylko się da wypłacaniu danego nominału poniżej limitu ostrzegawczego - czyli docelowo po to, abym zminimalizował ryzyko, że nie bedę mógł komuś wypłacić pieniędzy. Wobec tego, moim pomysłem jest zrobienie tylu kroków ile jest konkretnie wszystkich monet i banknotów, a nie tylu kroków ile jest dostępnych nominałów.

Zakładając najprostszy wariant rozwiązania, czyli utworzenie całej macierzy takiej jak pokazana na Wiki zjadłoby sporą ilość pamięci. Jednostką w której liczę pieniądze jest grosz, a monet i banknotów może być w sumie kilkaset. Zakładając wypłatę 500 zł, czyli 50 000 groszy i 500 monet i banknotów razem oraz mając 8 bajtów na każdy element macierzy dostaję zajętość pamięci równą: 50 000 * 500 * 8 B = 200 MB Chociaż w sumie to może i nie tak znowu dużo.

Macie jakieś ciekawe pomysły jak to rozwiązać?

Czy przypadkiem nie wystarczy stara dobra wersja greedy tego algorytmu? Czyli np. mając polskie nominały kwotę 29 rozmieniłbyś jako:
29 = (20) + 9 = (20) + (5) + 4 = (20) + (5) + (2) + 2 = (20) + (5) + (2) + (2).
Za każdym razem próbujesz dobrać jak największy dostępny nominał.

Dla nominałów, których używasz: {12, 5, 7, 4, 1} mamy:
29 = (12) + 17 = (12) + (12) + 5 = (12) + (12) + (5).

Zakładając, że mamy do wydania 60 zł i mamy do dyspozycji aktualnie tylko i wyłącznie banknoty 50 zł i 20 zł, to algorytm zachłanny nie da dobrej odpowiedzi.

A jeśli miałbym do wydania 60 zł, a do dyspozycji banknot 50 zł, banknot 10 zł i dużo banknotów 20 zł, to chciałbym to wydać banknotami 20zł, gdyż mam ich dużo, a banknot 50zł i banknot 10zł tylko po jednym.

Użyj algorytmu genetycznego ;)

Wibowit napisał(a):

A jeśli miałbym do wydania 60 zł, a do dyspozycji banknot 50 zł, banknot 10 zł i dużo banknotów 20 zł, to chciałbym to wydać banknotami 20zł, gdyż mam ich dużo, a banknot 50zł i banknot 10zł tylko po jednym.

Czyli chyba nie potrzebujesz nadawania priorytetu konkretnym monetom i banknotom, lecz nominałowi w zależności od liczby dostępnych sztuk?

Pytanie nr 1:
Co to zmieni w algorytmie?

Problem nr 2:
A czemu nie? W moim aktualnie wymyślonym algorytmie (niezaimplementowanym jeszcze) nadawanie priorytetów nominałom jest tak samo proste jak nadawanie priorytetów konkretnym monetom i banknotom, a jeśli zrobię to drugie to będę miał pewność że będzie tym czym chcę by było.

Załóżmy, że mam limit sprzętowy na każdy nominał 20 sztuk maksymalnie. Do tego dwa limity w programie: powyżej 15 sztuk jest nadwyżka, którą najlepiej jest się szybko pozbyć, a poniżej 5 jest limit ostrzegawczy czyli mam uważać żeby nie wydawać danego nominału pochopnie. No i wtedy myślę, żeby tym monetom z nadwyżki dać wysoki priorytet, a tym poniżej limitu ostrzegawczego niski.

proponuje algorytm dynamiczny odrobinę zmodyfikować. w standardowej wersji w talibcy trzymasz ile banknotów potrzeba aby wydać n złotych. gdy jakichś banknotów jest mało, to można pomnożyć tą ilość przez jakiś czynnik. np. w standardowej wersji aby wydać 6 zł mając 1, 2, 5 tworzymy tabelkę:
n 1 2 3 4 5 6
1 1 2 3 4 5 6
2 1 1 2 2 3 3
5 1 1 2 2 1 2
ale załóżmy, że nominałów 1 i 5 zł jest mało, dlatego traktujemy każdą taką monetę jak by była wydana np. 5 razy zamiast raz.
n 1 2 3 4 5 6
1 5 10 15 20 25 30
gdy dołoży 2 zł których jest dużo:
2 5 1 6 2 7 3
no i gdy dołożymy 5 (każdą traktujemy jak 5 monet):
2 5 1 6 2 5 3
jak widać algorytm wskazuje, że 6zł najlepiej wydać używając 3 monety 2 zł.
mam nadzieję, że jasno to wyraziłem.

No to jest mniej więcej rozwiązanie, które miałem na myśli, a więc nihil novum. Pytanie jakie to będzie mieć złożoności? Z tym, że dalej wolałbym przypisywać sobie priorytety do każdej monety/ banknotu osobno, a nie do całych nominałów.