Folosim cookie-uri pentru a vă asigura că aveți cea mai bună experiență de navigare pe site-ul nostru. Prin utilizarea site-ului nostru, recunoașteți că ați citit și înțeles Politica noastră privind cookie-urile și politica de confidențialitate

pentru

Într-un magazin de bomboane există N tipuri diferite de bomboane disponibile și sunt furnizate prețurile tuturor celor N tipuri diferite de bomboane. Există, de asemenea, o ofertă atractivă de către magazinul de bomboane. Putem cumpăra o singură bomboană din magazin și putem obține cel mult K alte bomboane (toate sunt diferite tipuri) gratuit.

  1. Găsiți suma minimă de bani pe care trebuie să o cheltuim pentru a cumpăra toate cele N bomboane diferite.
  2. Găsiți suma maximă de bani pe care trebuie să o cheltuim pentru a cumpăra toate cele N bomboane diferite.

În ambele cazuri, trebuie să utilizăm oferta și să recuperăm maximum de bomboane posibile. Dacă sunt disponibile k sau mai multe bomboane, trebuie să luăm k bomboane pentru fiecare cumpărare de bomboane. Dacă sunt disponibile mai puțin de k bomboane, trebuie să luăm toate bomboanele pentru o cumpărare de bomboane.

Exemple:

Un lucru important de remarcat este că trebuie să folosim oferta și să recuperăm maximum de bomboane pentru fiecare cumpărare de bomboane. Deci, dacă dorim să reducem la minimum banii, trebuie să cumpărăm bomboane la un cost minim și să obținem bomboane cu costuri maxime gratuit. Pentru a maximiza banii, trebuie să facem invers. Mai jos este un algoritm bazat pe acest lucru.

Imaginea de mai jos este o ilustrare a abordării de mai sus:

Mai jos este implementarea abordării de mai sus: