Question

Cerința
Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Pentru fiecare tip de bancnote se știe numărul de bancnote disponibile c[1] c[2] ... c[n]. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile.

Date de intrare
Programul citește de la tastatură numerele n și S, apoi valorile v[1] v[2] ... v[n] ale bancnotelor și apoi c[1] c[2] ... c[n].

Date de ieșire
Programul va afișa pe ecran n numere, reprezentând o modalitate de plată a sumei S. Fiecare număr x[i] va reprezenta numărul de bancnote de valoarea x[i] folosite pentru plata sumei S.

Restricții și precizări
1 ≤ n ≤ 6
1 ≤ S ≤ 1000
1 ≤ v[i] ≤ 100
1 ≤ c[i] ≤ 10
oricare variantă corectă de plată a sumei S va fi luată în considerare
pentru toate seturile de date există soluție



Exemplu
Intrare

5 375
1 5 10 50 100
6 3 4 6 1
Ieșire

5 0 2 5 1
Explicație
Se folosesc cinci bancnote de 1 leu, două de 10 lei, cinci de 50 de lei și una de 100 de lei: 5 * 1 + 2 * 10 + 5 * 50 + 1 * 100 = 375.

Problema 2245 de pe pbinfo.(C++)

Eu am doar 80 de puncte cu urmatoarea solutie daca va foloseste:
#include
using namespace std;
int numar_bancnote;
int suma;
int valori_bancnote[8];
int nrdisponibile_bancnote[8];
int cnrd[8];
void citire(int numar_operatii)
{
for (int numarator = 1; numarator <= numar_operatii; numarator++)
{
cin >> valori_bancnote[numarator];
}
for (int numarator2 = 1; numarator2 <= numar_operatii; numarator2++)
{
cin >> nrdisponibile_bancnote[numarator2];
cnrd[numarator2]=nrdisponibile_bancnote[numarator2];
}
}
void afisare()
{
for (int numarator4 = 1; numarator4 <= numar_bancnote; numarator4++)
{
cout << cnrd[numarator4]-nrdisponibile_bancnote[numarator4] << " ";
}
}
int main()
{
cin >> numar_bancnote >> suma;
citire(numar_bancnote);
for (int numarator3 = numar_bancnote; numarator3 >= 1; numarator3--)
{
if (valori_bancnote[numarator3] <= suma && nrdisponibile_bancnote[numarator3]!=0)
{
suma -= valori_bancnote[numarator3];
nrdisponibile_bancnote[numarator3]--;
numarator3++;
}
else if (suma == 0)
numarator3 = -1;
}
afisare();
return 0;
}

Answer 1

Ai avut noroc ca ai primit 80 de puncte.(probabil pe setul de date de test ai avut cateva locuri unde ai primit raspuns corect)

Aceasta problema este o problema clasica de tip greedy (problema bancnotelor).

Algoritmul este prezentat si problema rezolvata frumos aici:

https://www.geeksforgeeks.org/greedy-algorithm-to-find-minimum-number-of-coins/

Daca nu intelegi exact ce se petrece acolo ,ma poti contacta pe mail ([email protected])