Metoda Greedy si problema fractionara a rucsacului

Acest articol a fost adăugat de A Cosmina - vechi •miculprogramator Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

(Categoria Algoritmi si tehnici de programare, Autor Albulescu Cosmina)

• Conţinut:
• Despre algoritmii Greedy
• Problema spectacolelor
• Problema fractionara a rucsacului
• Precizari

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. 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.

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.

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

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.