the change-making problem se zabývá otázkou nalezení minimálního počtu mincí (určitých nominálních hodnot), které se přidávají k danému množství peněz. Jedná se o zvláštní případ problému celočíselného batohu a má aplikace širší než jen měna.
To je také nejčastější variace mince změnit problém, obecný případ oddíl, ve kterém, s ohledem na dostupné hodnoty z nekonečného souboru mince, cílem je zjistit počet možných způsobů, jak dělat změnu pro určité množství peněz, bez ohledu na pořadí mince.
provedení změny je minimalizační problém, zvolíme řešení, kde musíme dát minimální počet mincí pro danou částku.
- chamtivá metoda
2. Dynamická Metoda
dynamické programování
klasické dynamické programování strategie funguje vzhůru po nalezení kombinací všech menších hodnot, že by se součet na aktuální hranici.Tak, v každém prahu, všechny předchozí limity jsou potenciálně považována za práci, vzhůru k cíli částka W. z tohoto důvodu, tento dynamický přístup k programování může vyžadovat několik kroků, které je nejméně kvadratická v brance množství W.
optimální změnu mince, které Jsme viděli tento, chcete, aby se změny pomocí systému denominací, s použitím nejmenší počet mincí je to možné. Někdy chamtivý algoritmus poskytuje optimální řešení. Ale někdy to není — příkladem byl systém (12, 5, 1), kde dynamický algoritmus dává 15 = 12 + 1 + 1 + 1 ale lepší odpověď je 15 = 5 + 5 + 5. dynamika však vždy poskytuje optimální řešení nebo možné minimum mincí v rámci těchto jmenovatelů.
kroky: –
najdeme minimální číslo. mincí potřebných pro částku .
částka je částka, za kterou provádíme změnu.
nejprve nastavíme min. č. požadovaných mincí, tj., min = nekonečno
to znamená, že zpočátku nevíme, kolik mincí bude potřeba.
pak zkontrolujeme každou nominální hodnotu mincí a uvidíme, jestli ji lze použít k získání řešení.
Pokud je to možné, aktualizujeme proměnné min a mince.
Kde, min = minimální číslo. mince potřebné pro výrobu pro změnu množství
mince = první index mince v roztoku
Příklad:
Množství = 5
mince = {1,2,3}
Způsoby, jak změnit = 5
