problema schimbării abordează problema găsirii numărului minim de monede (de anumite denumiri) care se adaugă la o anumită sumă de bani. Este un caz special al problemei rucsacului întreg și are aplicații mai largi decât moneda.
este, de asemenea, cea mai frecventă variație a problemei schimbării monedei, un caz general de partiție în care, având în vedere denumirile disponibile ale unui set infinit de monede, obiectivul este de a afla numărul de modalități posibile de a face o modificare pentru o anumită sumă de bani, fără a lua în considerare ordinea monedelor.
efectuarea de modificări este o problemă de minimizare, alegem soluția în care trebuie să oferim minimum de monede pentru suma dată.
- metoda Greedy
2. Metoda dinamică
programare dinamică
o strategie clasică de programare dinamică funcționează în sus prin găsirea combinațiilor tuturor valorilor mai mici care ar însuma pragul curent.Astfel, la fiecare prag, toate pragurile anterioare sunt considerate potențial să funcționeze în sus până la valoarea obiectivului W. din acest motiv, această abordare de programare dinamică poate necesita un număr de pași care este cel puțin pătratic în suma obiectivului W.
schimbarea optimă a monedelor am văzut acest lucru, doriți să faceți schimbări folosind un sistem de denumiri, Folosind cel mai mic număr de monede posibil. Uneori algoritmul greedy oferă soluția optimă. Dar uneori nu — un exemplu a fost sistemul (12, 5, 1), unde algoritmul dinamic dă 15 = 12 + 1 + 1 + 1 dar un răspuns mai bun este 15 = 5 + 5 + 5. dar dinamic oferă întotdeauna o soluție optimă sau posibile monede minime în cadrul numitorilor.
pași:-
vom găsi minimul nr. de monede necesare pentru suma .
Suma este suma pentru care facem schimbarea.
vom seta mai întâi min. nu. de monede necesare adică., min = infinit
aceasta înseamnă că inițial nu știm câte monede vor fi necesare.
apoi vom verifica Fiecare monede denumire și a vedea dacă acesta poate fi folosit pentru a obține soluția.
dacă este posibil, atunci vom actualiza variabilele min și monede.
unde, min = minim nr. de monede necesare pentru a face schimbare pentru suma
monede = primul indice al monedei în soluție
exemplu:
suma = 5
monede = {1,2,3}
moduri de a face schimbare = 5
