/*
Algoritmi si tehnici de programare
---------------------------------------
[1] BKTR
--------------------------------------

[2] Greedy

Clasa problemelor rezolvabile Greedy

orice enunt de tip greedy este un enunt de optim
se cere gasirea unmui subset dintr-un set data astfel incat sa fie indeplinita o
anumita conditie
conditia solicitata in enunt  se numeste criteriul de optim global
solutia se obtine constructivist adica la fiecare pas executam o selectie a
unui cate nou element  din setul dat pentru a fi depus in solutie
selectia candidatului pentru a fi depus in solutie se executa
irevocabil pe baza unui criteriu de optim numit criteriul de optim local
Irevocabilitatea inseamna ca in cazul cat mai multe elemente
indeplinesc criteriul de optim local se alege primul dintre acestea
La o abordare de tip Greedy pentru a rula corect peste setul datelor
trebuie o justificare de natura matematica a faptului ca prin
aplicarea repetata a unui criteriu de optim local ceea ce construim in
solutie furnizeaza optimul global cerut de enunt.

Obs :
1) Irevocabilitatea inseamna ca daca tehnica ruleaza corect se va furniza
o singura solutie chiar daca eventual exista mai multe
2) In cazul in care criteriul de optim local aplicat in mod repetat nu conduce
intotdeauna la o solutie in care avem indeplinit criteriul de optim global
putem fi in situatiile :
        - in marea majoritate a cazurilor functioneaza corect
            sunt si cazuri particulare cand rezultatul nu este corect
            dar este admisbil
            ( o valoarea situata in apropierea optimului cerut de enunt )
        - in marea majoritate a cazurilor functioneaza corect
            sunt si cazuri particulare cand rezultatul nu este corect
            si nu este admisbil
        -  in marea majoritate a cazurilor functioneaza corect
           sunt si cazuri particulare cand rezultatul nu este gasit
           desi acesta exista

Greedy ca metode lucru are valoare practica cand
[a] functioneaza corect indiferent de forma datelor de intrare
[b] functioneaza corect in marea majoritate a cazurilor si poroblema este
      NP completa

Alg tip Greedy sunt foarte rapizi ( uneori pot fi imperfecti si admitem asta
                                   in anumite conditii )
furnizeaza solutii in timp uman acceptabil

De cele mai multe ori problemele sunt NP complete

De cele mai multe ori criteriul de optim local nu este explicat
formulat in enuntul problemei

Probleme de tip Greedy

1. problema rucsacului

enunt

"input.dat"
G greutatea maxima admisibila a rucsacului
n  un numar de obiecte
g1 p1   greutatea si profitului obiectului i
...
gn pn

Se cere se faca o alegere din setul celor n obiecte astfel acestea sa incapa
in rucsac ( suma greutatilor < G ) si profitul total sa fie maxim

varianta 1 ( continuum case )
depunem continuu obiecte in rucsac in baza criteriului de optim local
in cazul in care obiect curent selectat nu incape in fractionam
si actualizam profitul conform fractiei selectate

varianta 2 ( discret case )
admitem doar obiecte intregi in rucsac

========================================
problema rucsacului cazul continuu

alegem criteriul de optim local :

din subsetul celor ramase aleg un cel mai eficient obiect
definesc eficienta castigul obtinut pe unitatea de greutate

In cazul in care pentru criteriul de optim local ales acesta este
aplicat identic peste subsetul celor nealese inca
Greedy poate fi optimizata presortand datele in baza criteriului pentru
optimul local

In Problema rucsacului cazul continuu presortam obiectele dupa eficienta


int G;
int n;
float O[100][4]; // pe coloana 1 este numele obiectului
                          //                     2 greutatea
                          //                     3 profitul
                         //                      4 eficienta
int read_data()
{

}

int sort_data()
{


}

int compute_data()
{
// Greedy  ?

}

int main()
{
read_data();
sort_data();
compute_data();
}


*/