Difference between revisions of "Clasa a XI-a lecția 7"

From Algopedia
Jump to: navigation, search
(Created page with "= Metoda Greedy = Algoritmii aplicaţi problemelor de optimizare sunt, în general, compuşi dintr-o secvenţă de paşi, la fiecare pas existând mai multe alegeri posibile...")
 
(No difference)

Latest revision as of 09:56, 4 November 2019

Metoda Greedy

Algoritmii aplicaţi problemelor de optimizare sunt, în general, compuşi dintr-o secvenţă de paşi, la fiecare pas existând mai multe alegeri posibile. Un algoritm greedy va alege la fiecare moment de timp soluţia ce pare a fi cea mai bună la momentul respectiv. Deci este vorba despre o alegere optimă, făcută local, cu speranţa că ea va conduce la un optim global. Acest capitol tratează probleme de optimizare ce pot fi rezolvate cu ajutorul algoritmilor greedy. Algoritmii greedy conduc în multe cazuri la soluţii optime, dar nu întotdeauna.

Enunt general

Să considerăm o mulţime A cu n elemente. Se cere o submulţime Sol a sa cu m elemente, unde m <= n; astfel încât să fie îndeplinite anumite condiţii (condiţiile diferă de la o problemă la alta).

Sol ← Ø
cât timp ( nu am completat solutia Sol ) 
  Aleg din A un x ca fiind cel mai bun element disponibil
    dacă ( x satisface restrictiile problemei ) atunci 
      Adaugam x la Sol

Descriere: Initial solutia Sol este vida si pe rand aleg, dintre elementele multimii A, cate un element, cel mai bun la momentul respectiv, pana cand se obtine solutia ceruta.

Observatii

  • Datorita faptului ca solutia este construita pas cu pas fara un mecanism de revenire ca la Backtraching, metoda se numeste Greedy (in romana Greedy = lacom )
  • Desi s-a prezentat forma generala a metodei, ea nu poate fi standardizata ( nu avem o rutina unica pe care sa o aplicam la rezolvarea oricarei probleme)
  • Metoda Greedy poate di folosita:
    • cand stim sigur ca se ajunge la solutia sorita ( avem la baza o demonstratie )
    • atunci cand nu dispunem de o solutie in timp polinomial, dar prin Greedy obtinem o solutie acceptabila, nu neaparat optima ( Greedy euristic ).


Probleme pentru care metoda Greedy conduce la solutia optima

Problema Suma maximă

Se consideră o mulţime A cu n numere reale. Se cere o submulţime S care sa contina un număr maxim de elemente, astfel încât suma elementelor sale să fie maximă. Exemplu. Pentru numerele 1 -7 6 2 -5 8 . Soluția este : Se aleg numerele pozitive: răspunsul este 1 6 2 8 ( suma 17 )

Problema 2 suma maximă

Se consideră o mulțime de n numere reale. Se cere o submulțime a sa cu m elemente, astfel încât suma elementelor din submulțimea S să fie maximă. Exemplu : Daca avem elementele: 1 -1 2 4 -2 si m = 4 Soluție: Alegem cele mai mari m elemente: 4 2 1 -1

Problema Spectacolelor Spectacole

La un festival sunt programate n spectacole, pentru fiecare se cunoaşte momentul de început și momentul de sfârșit, exprimate prin numere naturale. Un spectator dorește să urmărească cât mai multe spectacole în întregime.

Determinați numărul maxim de spectacole care pot fi urmărite, fără ca acestea să se suprapună.


#include <fstream>
#include <algorithm>

using namespace std;

int n,i,aux,k;
struct spectacol{
    int x, y;
} v[105];

bool cmp(const spectacol a, const spectacol b){
 return a.y < b.y;
}
int main(){
  ifstream f("spectacole.in");
  ofstream g("spectacole.out");
  f >> n;
  for( i = 1; i <= n; i++ ) 
    f >> v[i].x >> v[i].y;
  sort( v + 1, v + n + 1, cmp );
  for( i = 1; i <= n; i++ )
    if( v[i].x >= aux ){
      k ++;
      aux = v[i].y;
    }
    g << k;
    return 0;
}

Problema Proiectelor Proiecte

Cunoscând timpii de evaluare a n proiecte, să se stabilească ordinea de evaluare a acestora, astfel încât să se minimizeze timpul mediu de aşteptare a investitorilor care au depus aceste proiecte.

// Sortam proiectele crescator dupa timpul necesar analizarii acestora
// impreuna cu numerele de ordine ale acestora

#include <bits/stdc++.h>

using namespace std;

int v[1004];   // v[i] - timpul necesar analizarii proiectului
int p[1004];   // p[i] - nr proiectului

ifstream fin ( "proiecte.in" );
ofstream fout ( "proiecte.out" );

bool cmp( int a, int b ){
  return v[a] < v[b];
}

int main(){
  int n, i;
  fin >> n;
  for( i = 0; i < n; i++ ){
    fin >> v[i];
    p[i] = i;
  }
  sort( p, p + n, cmp );
  for( int i = 0; i < n; i++ )
    fout << p[i] + 1 << ' ';
  return 0;
}

Tema

Tema Teorie

Primele 4 probleme de la cap greedy de pe pbinfo

Tema Laborator

http://varena.ro/problema/sume http://varena.ro/problema/cafea

De sortat http://varena.ro/cauta-probleme?tag_id[]=1089

Codeforces

(laborator teorie )

  • Team banal (clasa a 5-a)