Tehnica Greedy

Referat
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: docx
Pagini : 5 în total
Cuvinte : 836
Mărime: 40.11KB (arhivat)
Publicat de: Denisa B.
Puncte necesare: 5

Extras din referat

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.

Preview document

Tehnica Greedy - Pagina 1
Tehnica Greedy - Pagina 2
Tehnica Greedy - Pagina 3
Tehnica Greedy - Pagina 4
Tehnica Greedy - Pagina 5

Conținut arhivă zip

  • Tehnica Greedy.docx

Te-ar putea interesa și

Arbori Huffman - Implementare în C++

INTRODUCERE În lucrarea de fața tratez metodele Huffman de codificare și comprimare a datelor, necesare pentru elaborarea unor algoritmi optimi...

Algoritmul de Compresie Huffman

1.1 Noţiuni introductive 1.1.1 Terminologie Pentru a evita eventualele neînţelegeri ce ar putea rezulta din utilizarea unor termeni care sunt...

Turbo Pascal - metoda backtracking - tehnica Greedy

Aparitia limbajului Pascal este un raspuns la criza care a aparut in domeniul programarii calculatoarelor , la sfarsitul anilor ’60 . Limitarile...

Algoritmi și Structuri de Date

Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...

Algoritmi GREEDY

Pusi in fata unei probleme pentru care trebuie sa elaboram un algoritm, de multe ori "nu stim cum sa incepem". Ca si in orice alta activitate,...

Proiectarea Algoritmilor

1. INTRODUCERE ÎN PROIECTAREA ALGORITMILOR 1.1. Definiţii Un algoritm este o metodă de rezolvare pas cu pas a problemelor. O problemă este...

Structuri de Date și Analiza Algoritmilor

8. Arbori 8.1. Arbori generalizaţi 8.1.1. Definiţii În definirea noţiunii de arbore se porneşte de la noţiunea de vector. Fie V o mulţime având...

Algoritmi pentru Optimizarea Rețelelor de Comunicații

Pe parcursul acestui capitol se vor prezenta soluţii matematice şi computaţionale, care au drept scop optimizarea reţelelor de comunicaţii la...

Ai nevoie de altceva?