h1. Metoda Greedy si problema fractionara a rucsacului
 
== include(page="template/implica-te/scrie-articole" user_id="miculprogramator") ==
 
(Categoria _Algoritmi si tehnici de programare_, Autor Albulescu Cosmina)
 
(toc){width: 25em}*{text-align:center} *Conţinut:*
* 'Despre algoritmii Greedy':metoda-greedy-si-problema-fractionara-a-rucsacului#despre-algoritmii-greedy
* 'Problema spectacolelor':metoda-greedy-si-problema-fractionara-a-rucsacului#problema-spectacolelor
* 'Problema fractionara a rucsacului':metoda-greedy-si-problema-fractionara-a-rucsacului#problema-fractionara-a-rucsacului
* 'Precizari':metoda-greedy-si-problema-fractionara-a-rucsacului#precizari
 
 
 
 

h1. Despre algoritmii Greedy

Algoritmii Greedy sunt caracterizati de metoda lor de functionare: la fiecare pas se alege cel mai bun candidat posibil, dupa evaluarea tuturor acestora. Algoritmii sunt rapizi, insa nu intotdeauna optimi. Cand nu aveti o idee mai buna legata de o problema, in timpul unui concurs, o implementare Greedy ar putea aduce in jur de 30% din punctaj.
Exista situatii in care algoritmii clacheaza, cum ar fi problema comisului voiajor, sau problemele NP-complete.

Algoritmii Greedy sunt caracterizati de metoda lor de functionare: la fiecare pas se alege cel mai bun candidat posibil, dupa evaluarea tuturor acestora. Metoda determina intotdeauna o singura solutie, asigurand un optim local, dar nu intotdeauna si global. Tehnica Greedy este una de optimizare, ruland mai rapid decat un Backtraking, dar nefiind intotdeauna cea mai buna.
 
Cand nu aveti o idee mai buna legata de o problema, in timpul unui concurs, o implementare Greedy ar putea aduce in jur de 30% din punctaj.
Exista situatii in care acesti algoritmi clacheaza, cum ar fi problema comisului voiajor sau problemele NP-complete.
 
Metoda Greedy are si avantaje: poate fi aplicata multor probleme: determinarea celor mai scurte drumuri in grafuri (Dijkstra), determinarea arborelui minimal de acoperire (Prim, Kruskal), codificare arborilor Huffmann, planificarea activitatilor, problema spectacolelor si problema fractionara a rucsacului. Dintre acestea, articolul le trateaza numai pe ultimele doua pentru a da un exemplu cat mai bun a modului de functionare si aplicare a algoritmilor Greedy.

Metoda Greedy are si avantaje: poate fi aplicata multor probleme: determinarea celor mai scurte drumuri in grafuri (Dijkstra), determinarea arborelui minimal de acoperire (Prim, Kruskal), codificare arborilor Huffmann, problema spectacolelor si problema fractionara a rucsacului. Dintre acestea, articolul le trateaza numai pe ultimele doua.

*Mishu91*: Nu ştiu dacă sunt cea mai în măsură persoană să îmi dau cu părerea, însă eu zic că prezentarea este mult prea sumară, iar problemele alese sunt cam puţine la număr(doar 2) şi nu foarte relevante. În plus, identarea nu este cea mai fericită, insă asta nu este o problemă foarte mare.

h1. Problema spectacolelor

	return 0;
}
==

 
h1. Problema fractionara a rucsacului
 
Se considera ca dispunem de un rucsac cu capacitatea M si de N obiecte, definite fiecare prin greutate si valoare, ce trebuie introduce in rucsac. Se cere o modalitate de a umple rucsacul cu obiecte , astfel incat valoarea totala sa fie maxima. Este posibil ca oricate obiecte si bucati din obiecte sa fie introduse.
 
h2. Date de intrare
 
Pe prima linie a fisierului de intrare _rucsac.in_ se gasesc doua numere, primul fiind N, iar al doilea M (cu specificatiile din enunt). Pe urmatoarele N linii se gasesc, despartite printr-un spatiu valoarea obiectului curent si greutatea acestuia.
 
h2. Date de iesire
 
In fisierul de iesire _rucsac.out_ vor fi specificate numarul de ordine al obiectului, precum si procentul in care acesta poate fi introdus in rucsac.
 
h2. Exemplu
 
|_. rucsac.in | |_. rucsac.out |
| 5 100
1000 120
500 20
400 200
1000 100
25 1|          | 2 100
                 4 79
                 5 100 |
 
h2. Descrierea solutiei
 
Vom reprezenta solutia problemei ca pe un vector x. Vom ordona obictele descrescator tinand cont de valoarea/greutate. Atata timp cat obiectele incap in rucsac, le vom adauga in intregime. Completam rucsacul cu un fragment din urmatorul obiect ce nu a fost deja selectat.
 
O implementare simpla a acestui algoritm este urmatoarea:
 
 
==code(cpp) |
 
#include <iostream>
#include <fstream>
using namespace std;
 
ifstream f("rucsac.in");
ofstream g("rucsac.out");
 
int o[100],N,M;
float val[100],greu[100],x[100],Gr;
 
void  citeste()
{
	int i;
	f>>N>>M;
	for (i=0;i<N;++i)
	{
		o[i]=i;
		f>>val[i]>>greu[i];
	}
	f.close();
}
 
void sort()
{
	int i,aux,schimb;
	do
	{
		schimb=0;
		for (i=0;i<N-1;++i)
			if (val[o[i]]/greu[o[i]]<val[o[i+1]]/greu[o[i+1]])
			{
				aux=o[i];
				o[i]=o[i+1];
				o[i+1]=aux;
				schimb=1;
			}
	}
	while (schimb);
}
 
void rezolva()
{
	int i;
	for (i=0,Gr=M;i<N && Gr>greu[o[i]];++i)
	{
		x[o[i]]=1;
		Gr-=greu[o[i]];
	}
}
 
void afisare()
{
	int i;
	for (i=0;i<N;++i)
		if (x[i]) g<<i+1<<" "<<x[i]*100<<endl;
	g.close();
}
 
int main()
{
	citeste();
	sort();
	rezolva();
	afisare();
	return 0;
}
 
==
 
h1. Precizari
 
Desi tehnica Greedy poate fi abordata cu succes in abordarea problemei fractionare a rucsacului, nu la fel se poate spune si in cazul problemei discrete a rucsacului. Aceasta se poate rezolva optim cu ajutorul programarii dinamice.
 
In cazul problemei comisului voiajor, putem aplica metoda Backtracking, Greedy nefiind optim. Spre deosebire de algoritmii "lacomi", tehnicile Backtracking revin mereu inapoi, la nivel de predeceosor, de aici rezultand timpul mare de executie in comparatie cu Greedy. Un lucru pe care il au comun ambele metode este acela ca solutia se construieste progresiv, pas cu pas.