Problema restului
Un casier care dă restul ia cea mai mare monedă care încape, apoi pe următoarea, iar pentru euro sau dolari asta dă mereu cele mai puține monede. Schimbați însă monedele în 1, 3 și 4, și același obicei plătește 6 cu trei monede, când ar ajunge două. Programarea dinamică găsește adevăratul minim pentru orice monede.
Două întrebări
Problema restului are două variante. Prima cere cele mai puține monede care formează o sumă exactă; este cunoscută și ca problema schimbului de monede. A doua întreabă câte combinații diferite de monede formează suma. În ambele, fiecare tip de monedă poate fi folosit de oricâte ori, iar ambele se rezolvă construind răspunsul pentru fiecare sumă din răspunsurile pentru sume mai mici.
Cele mai puține monede, pas cu pas
Faceți un rând de celule pentru sumele de la 0 până la țintă. Suma 0 necesită 0 monede; orice altă sumă pornește de la infinit. Parcurgeți sumele în ordine și, pentru fiecare, încercați fiecare monedă c care încape: celula pentru suma minus c, plus o monedă, este un candidat. Păstrați-l pe cel mai mic. Fiecare celulă depinde doar de celule aflate la stânga ei, care sunt deja definitive, deci o singură trecere completează rândul.
Un exemplu
Cu monedele 1, 3 și 4: suma 1 necesită 1 monedă, 2 necesită 2, 3 necesită 1 (o singură monedă de 3), iar 4 necesită 1. Pentru 5 se încearcă 1 (4 necesită 1, deci 2 monede), 3 (2 necesită 2, deci 3 monede) și 4 (1 necesită 1, deci 2 monede): cel mai bun rezultat este 2. Pentru 6 se încearcă 1 (5 necesită 2, deci 3), 3 (3 necesită 1, deci 2) și 4 (2 necesită 2, deci 3): cel mai bun rezultat este 2, prin 3 + 3. Greedy ar fi plătit 4 + 1 + 1.
Numărarea modurilor
Pentru a număra combinațiile, adăugați monedele una câte una. Doar cu prima monedă, fiecare sumă poate fi obținută într-un singur mod sau deloc. Când se adaugă o monedă nouă c, modurile de a obține o sumă a sunt modurile vechi, fără c, plus modurile de a obține a − c cu c permisă din nou, pentru că fiecare dintre ele devine un mod de a obține a prin adăugarea încă unei monede c. Cu monedele 1, 2 și 5 există 4 moduri de a obține 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 și 1 + 1 + 1 + 1 + 1.
Când ajunge metoda greedy
Un sistem de monede pentru care greedy dă mereu cele mai puține monede se numește canonic. Majoritatea monedelor naționale moderne sunt concepute astfel, iar în 1994 David Pearson a descris un test care verifică un sistem de monede într-un număr de pași ce crește doar polinomial cu numărul de monede. Vechile monede britanice nu erau canonice: greedy plătește 48 de pence cu o jumătate de coroană, un șiling și un sixpence, când ar ajunge doi florini.
Explorați
Deschideți aplicația, treceți la vizualizarea Tabel și apăsați Pas. În modul Cele mai puține monede, celula portocalie este suma calculată în acel moment, iar celula albastră este suma mai mică pe care o lasă moneda; rândul de dedesubt păstrează ultima monedă, iar la final monedele se citesc înapoi de-a lungul lui. Treceți la Număr de moduri și urmăriți cum cresc valorile rând cu rând, pe măsură ce se adaugă fiecare monedă.
Întrebări frecvente
Este problema restului o problemă a rucsacului?
O rudă apropiată. Varianta cu cele mai puține monede este o problemă a rucsacului nemărginit, în care fiecare monedă este un obiect a cărui greutate este valoarea ei nominală, rucsacul trebuie umplut exact, iar scopul este un număr cât mai mic de obiecte.
Care este complexitatea în timp?
O(k·A) pentru k tipuri de monede și o sumă A, în ambele variante. Tabelul pentru cele mai puține monede are A + 1 celule, iar cel pentru moduri (k + 1)·(A + 1), deși ajunge un singur rând dacă celulele sunt actualizate pe loc.
De ce se numără monedele într-o ordine fixă?
Dacă fiecare sumă ar încerca fiecare monedă, 1 + 2 și 2 + 1 ar fi numărate ca două moduri. Adăugând monedele câte un rând pe rând, o combinație este construită mereu întâi din monedele anterioare, așa că fiecare este numărată exact o dată.
Se pot citi înapoi monedele pentru numărul de moduri?
Nu ca un singur răspuns, pentru că sunt multe. Varianta cu cele mai puține monede păstrează ultima monedă a fiecărei sume, iar asta ajunge pentru a reconstrui o combinație optimă.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați problema restului