Am rezolvat problema schimbului de monede. Condiția este dată mai jos. Problema este că toate soluțiile pe care le-am experimentat au multă memorie. Și nu se aplică datelor de intrare mari, de exemplu, pentru 1.000.000.000. Întrebarea este cum puteți optimiza soluțiile pentru numerele mari? Sau poate exista o idee mai eficientă pentru rezolvarea acestei probleme?
Conform numerelor 1≤n≤30 și 1≤w≤10 ^ 9 și găsim numărul minim k pentru setul de numere 1≤v [1], ..., v [n] ≤10 ^ 9. pentru care numărul w poate fi reprezentat ca suma de numere k din set. Fiecare număr din set poate fi folosit de câte ori doriți. Se știe că există o unitate în set și că pentru orice pereche de numere din set, una dintre ele este împărțită în alta. Se garantează că în răspunsul optim numărul de termeni nu depășește 10 ^ 4.
Afișați numărul k și sumele în sine.
Nu sunt necesare mese intermediare:
Datorită faptului că întotdeauna împărțim țintă la cel mai mare posibil, rezultatul este întotdeauna incrementat de cel mai mic număr posibil. În cele din urmă, avem o condiție.
În lista de monede selectate sunt incluse cele care sunt mai mici decât ținta țintă - odată ce moneda este mai mică, ea poate fi schimbată.
De ce produce algoritmul cea mai bună soluție? Deoarece starea spune:
Pentru orice pereche de numere dintr-un set, unul dintre ele este împărțit în altul
Aceasta înseamnă că orice număr din set este divizibil cu orice număr din set mai mic decât primul. De fapt, numărul înainte de 1 trebuie să fie GCD al tuturor numerelor. Prin urmare, avem dreptul să le rezolvăm și să acționăm după cum sugerez. Dacă nu ar fi avut GCD, atunci da, ar fi necesar să rezolve opțiunile pentru schimb.
răspunsul este 7 decembrie 15 la ora 9:57
Trimiteți-le prietenilor: