Tehnica Greedy

Extras din referat Cum descarc?

Cerinta: Un bijutier are la dispozitie N bucati de metal pretios. Pentru fiecare bucata i de metal el cunoaste greutatea gi (in grame) si pretul pi (in $) . Din aceste metale el trebuie sa confectioneze un colier impletit, avand greutatea G impusa de catre cumparator. Stiind ca bijuteria trebuie realizata cu un cost minim, sa se precizeze cum foloseste bijutierul bucatile de metal pretios. 
Obs.Bucatile de metal pretios pot fi folosite in intregime sau numai partial.
Date de intrare:fisierul date.in contine:-pe prima linie doua numere naturale N si G, cu semnificatia din enunt;-pe urmatoarele N linii triplete de numere naturale de forma id g p, unde unde id reprezinta identificatorul unui metal, g greutatea acestuia, iar p pretul sau integral.
Date de iesire:fisierul date.out contine pe fiecare linie identificatorul unui metal selectat si procentul in care au fost inclus in bijuterie. Pe ultima linie se scrie valoarea totala a acesteia.
Rezolvare:
Primul pas facut in rezolvarea problemei este creearea structurii care include : id-ul, greutatea gi si pretul pi al materialelor, mai tarziu am adaugat o noua variabila numita raport, care va reprezenta pretul pe gramaj al metalelor. Am citit datele din fisierul date.in si am caculat raportul pi/gi. Am sortat datele de intrare cu ajutorul functiei qsort,in ordine descrescatoare dupa raport deoarece se cere realizarea colierului cu pretul minim. 
Apoi am facut functia de tip void denumita greedy:
void greedy(FILE*o, bijuterie b[101], int n, int g)
{
int i=0, g_colier=0;
float pret_biju = 0;
while(i<n && g_colier <= g)
{
if(g_colier + b[i].gi <= g)
{
g_colier += b[i].gi;
pret_biju += b[i].pi;
fprintf(o, "%d 100%%\n", b[i].id);
}
else {
pret_biju += (g - g_colier) * b[i].raport;
float proc = ((g - g_colier) * b[i].raport)*10;
fprintf(o, "%d %.3f%% \n",b[i].id, proc);
g_colier = g;
}
i++;
}
fprintf(o, "%.3f", pret_biju);
}
Unde g_colier reprezinta greutatea curenta si pret_biju, pretul curent ale colierului.
S-a aplicat tehnica greedy deoarece cat timp g_colier nu a ajuns la g, greutatea ceruta, se aduga pe rand cate un metal pana cand s-a ajuns la greutatea ceruta sau pana cand mai este nevoie doar de o bucata din material. Pentru a calcula pretul bucatii necesare se scade din greutatea finala greutatea curenta si se inmulteste cu raportul specific metalului. La fina am afisat pretul final al colierului.

Fisiere in arhiva (1):

 Tehnica Greedy.docx