Diferente pentru metoda-greedy-si-problema-fractionara-a-rucsacului intre reviziile #1 si #2

Diferente intre titluri:

aici-vreau-sa-fie-articolul-meu
Metoda Greedy si problema fractionara a rucsacului

Diferente intre continut:

Scrie aici despre aici-vreau-sa-fie-articolul-meu
h1. 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.
 
h1. 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.
 
h2. 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.
 
h2. 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.
 
h2. Restrictii
 
* n <= 100
* spectacolele sunt numerotate de la 1 la n
 
h2. Exemplu
 
|_. spectacole.in | |_. spectacole.out |
| 5
12 30 16 30
15 0 18 0
10 0 18 30
18 0 20 45
12 15 13 0 |         | 5 2 4 |

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.