Created
March 14, 2026 10:02
-
-
Save thinkphp/5db8a3804b52a8eb18161c426073d971 to your computer and use it in GitHub Desktop.
Greedy.cpp Teorie
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Greedy | |
| ------ | |
| Se considera o multime A. Se cere o submultime a sa astfel incat sa fie indeplinite anumite conditii (acestea difera de la o problema la alta). | |
| Structura generala a unei aplicatii Greedy este data mai jos: | |
| sol := Multimea Vida (0) | |
| REPETA | |
| Alege x apartine lui A | |
| daca este Posibil atunci Sol <--- Sol + x | |
| Pana cand am obtinut Solutia | |
| Afiseaza solutia | |
| Solutia este initial VIDA si, pe rand, se alege, dintre elementele multimii A, element cu element, pana cand se obtine solutia ceruta | |
| ----> se regula metoda Greedy rezolva problema in timp O(n^k) | |
| ----> datorita faptului ca solutia este construita pas cu pas , fara un mecanism de revenire ca la backtracking, metoda se numeste Greedy | |
| ---> exemplu clasic | |
| Se conside o multime de n numere REALE. Se cere o submultime a sa, | |
| cu un numar maxim de elemente, astfel incat suma elementelor sa fie maxima. | |
| M = -1, 2, 3, 4, 5, -2, -7, 10, -10 | |
| */ | |
| #include <iostream> | |
| using namespace std; | |
| float M[100], B[100]; | |
| int n, m, i; | |
| void GREEDY() { | |
| for(int i = 1; i <= n; ++i) { | |
| if(M[i] >= 0) { | |
| m++; | |
| B[m] = M[i]; | |
| } | |
| } | |
| } | |
| int main() { | |
| cout<<"n="; | |
| cin>>n; | |
| for(int i = 1; i <= n; ++i) cin>>M[i]; | |
| GREEDY(); | |
| for(int j = 1; j <= m; j++) cout<<B[j]<<" "; | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment