[C++] Metoda Greedy

[Dookie]

Metoda Greedy este una din cele mai directe tehnici de proiectare a algoritmilor care se aplica la o varietate larga de probleme.In general,aceasta metoda se aplica problemelor de optimizare.Specificul acestei metode consta in faptul ca se construieste solutia optima pas cu pas,la fiecare pas fiind selectat(sau „inghitit”) in solutie elementul care pare „cel mai bun”la momentul respectiv,in speranta ca va duce la solutie optima globala.

 

Pentru a fi totul mai clar, luam un exemplu. Consideram urmatoarea problema:

 

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 (n <= 100) 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.

#include<fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

struct spectacol
{
int s,d;
};

void citire(int &n, spectacol a[])
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>a[i].s>>a[i].d;
}

void ordonare(int n, spectacol a[])
{
int i,j;
spectacol aux;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(a[i].d>a[j].d)
{
aux=a[i]; a[i]=a[j]; a[j]=aux;
}
}

void afisare(int n, spectacol a[])
{
for(int i=1;i<=n;i++)
fout<<a[i].s<<","<<a[i].d<<" ";
}

void greedy(int n, spectacol a[])
{
spectacol s[100];
int i,k;
k=1;
s[1]=a[1];
for(i=2;i<=n;i++)
if(s[k].d<a[i].s) s[++k]=a[i];
afisare(k,s);
}

int main()
{
int n;
spectacol a[100];
citire(n,a);
ordonare(n,a);
greedy(n,a);
fin.close();
fout.close();
}

Daca aveti nelamuriri va rog sa imi lasati aici in comentarii.

Daca doriti puteti sa imi trimiteti PM cu aplicatii C/C++/JavaScript/HTML/CSS/C#/Pascal si voi incerca sa va explic cat mai pe inteles.

O zi placuta in continuare si spor.

[SwiftBrotherHD]

Topic aproved! Multumim Dookie.