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.

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.

Problema spectacolelor

Managerul artistic al unui festival trebuie sa selecteze o multime cat mai ampla de spectacole ce pot fi jucate in singura sala pe care o are la dispozitie.Stiind ca i s-au propus n spectacole si pentru fiecare spectacol i-a fost anuntat intervalul in care se poate desfasura [Si, Fi] (Si reprezinta ora si minutul de inceput, iar Fi ora si minutul de final al spectacolului i), scrieti un program care sa permita spectatorilor vizionarea unui numar cat mai mare de spectacole.

Date de intrare

Pe prima linie a fisierului de intrare spectacole.in se afla numarul n, numarul de spectacole propus. Pe urmatoarele n linii se vor afla 4 valori, primele doua reprezentand ora si minutul inceperii spectacolului curent, iar ultimele doua reprezentand ora si minutul terminarii spectacolului.

Date de iesire

Fisierul de iesire spectacole.out contine o singura linie, pe aceasta vor fi scrise numerele de ordine ale spectacolelor care indeplinesc solutia problemei, printr-un spatiu.

Restrictii

• n <= 100

Exemplu

Descrierea solutiei

Vom sorta crescator spectacolele dupa ora de final. Vom selecta initial primul spectacol (cel care se termina cel mai devreme). In continuare vom selecta, la fiecare pasa, primul spectacol neselectat, care nu se suprapune peste cele deja selectate.

O implementare intuitiva a acestui algoritm va fi prezentata in continuare. Pentru sortat vom folosi metoda BubbleSort, care este indeajuns de buna pentru limitele impuse de problema.

#include <iostream>
#include <fstream>
using namespace std;

ifstream f("spectacole.in");
ofstream g("spectacole.out");

int n,inceput[100],sfarsit[100],nr[100];

void citeste()
{
	int ora,min,i;
	f>>n;
	for (i=0;i<n;++i)
	{
		nr[i]=i+1;
		f>>ora>>min;
		inceput[i]=ora*60+min;
		f>>ora>>min;
		sfarsit[i]=ora*60+min;
	}
	f.close();
}

void sorteaza()
{
	int aux,schimb,i;
	do
	{
		schimb=0;
		for (i=0;i<n-1;++i)
			if (sfarsit[nr[i]]>sfarsit[nr[i+1]])
			{
				aux=nr[i];
				nr[i]=nr[i+1];
				nr[i+1]=aux;
				schimb=1;
			}
	}
	while (schimb);
}

void rezolva()
{
	int ultim,i;
	for (ultim=0,i=1;i<n;++i)
		if (inceput[nr[i]]>=sfarsit[nr[ultim]])
		{
			g<<nr[i]+1<<" ";
			ultim=i;
		}
	g<<endl;
}

int main()
{
	citeste();
	sorteaza();
	rezolva();
	return 0;
}

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.

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.

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.

Exemplu

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:

#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;
}