Tehnica Greedy

Cerinta: Un bijutier are la dispoziție N bucăți de metal prețios. Pentru fiecare bucată i de metal el cunoaște greutatea gi (in grame) și prețul pi (in $) . Din aceste metale el trebuie să confecționeze un colier împletit, având greutatea G impusă de către cumpărător. Știind că bijuteria trebuie realizată cu un cost minim, să se precizeze cum folosește bijutierul bucățile de metal prețios.

Obs.Bucățile de metal prețios pot fi folosite în întregime sau numai parțial.

Date de intrare:fișierul date.in conține:-pe prima linie două numere naturale N și G, cu semnificația din enunț;-pe următoarele N linii triplete de numere naturale de forma id g p, unde unde id reprezintă identificatorul unui metal, g greutatea acestuia, iar p prețul sau integral.

Date de ieșire:fișierul date.out conține pe fiecare linie identificatorul unui metal selectat și procentul în care au fost inclus în bijuterie. Pe ultima linie se scrie valoarea totală 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.