Tehnica greedy

Se aplica problemelor in care se da o multime A continand n date de intrare si se cere sa se determine o submultime a sa (B) care satisface anumite conditii pentru a fi acceptata. Aceasta submultime se numeste solutie posibila. Se cere sa se determine o solutie posibila care fie sa maximizeze fie sa minimizeze o anumita functie obiectiv data. Aceasta solutie posibila se numeste solutie optima.

Obs: Metoda Greedy nu cauta sa determine toate solutiile posibile ( care ar putea fi prea numeroase) si apoi sa aleaga din ele pe cea optima, ci cauta sa introduca pe rand un element x (il ,,inghite") in solutia optima.

Metoda Greedy lucreaza in pasi astfel:

1.se initializeaza multimea solutiilor (B) cu multimea vida (B=- )

2.se alege un anumit element x- A

3.se verifica daca elementul ales poate fi adaugat la multimea solutiilor, daca da atunci va fi adaugat (B=B- {x})

4.procedeul continua astfel, repetitiv, pana cand au fost determinate toate elementele din multimea solutiilor.

Exemplul nr. 1

Se da o multime X = {x1, , xn} cu elemente reale. Se cere sa se determine o submultime Y - X astfel incat sa fie maxima.

Observam ca o solutie posibila Y - X va fi o submultime Y - X cu toate elementele pozitive.

#include<iostream.h>

int n, k, x[100], y[100];void main ( )

void citire ( ){

{citire ( );

cin>>n;k = 0;

int i;for (i=1;i<=n;i++)

for (i=1;i<=n;i++)if(x[i]>0) {k++;

cin>>v[i]; y[k] = x[i];}

} }

Exemplul nr.2

Problema platii unei sume cu bancnote(monezi) de valoare data: sa se efectueze plata unei sume S utilizand un numar minim de bancnote (monezi). Valorile lor se cunosc.

Metoda Greedy se poate aplica astfel:

1.Fie suma care a mai ramas de platit X=S

2.Se alege moneda de valoare maxima Mi (astfel incat Mi<=X)

3. Se calculeaza nr. maxim de monezi Mi ce pot fi date (n = X div Mi )

4.Repetam pana cand restul sumei de plata e zero

Presupunem ca avem urmatoare lista de bancnote disponibile: 100lei, 50lei, 10lei, 1leu. De asemenea, din fiecare tip de moneda avem un numar nelimitat de bucati.

void Greedy(int suma)

{

int nr_bancnote;

nr_bancnote = suma/100;

cout<<"s-au platit bancnote de 100"<< nr_bancnote;

suma = suma%100;

nr_bancnote = suma/50;

cout<<"s-au platit bancnote de 50"<< nr_bancnote;

suma = suma%50;

nr_bancnote = suma/10;

cout<<"s-au platit bancnote de 10"<< nr_bancnote;

suma = suma%10;