backtracking
#include <iostream> using namespace std; const int TOTAL = 10; // 5 fete + 5 băieți const int GROUP_SIZE = 5; // Lista studenților cu identificatori unici fără folosirea pointerilor char students[TOTAL][3] = { "F1", "F2", "F3", "F4", "F5", "B1", "B2", "B3", "B4", "B5" }; int solution[GROUP_SIZE]; // Funcție care verifică dacă soluția parțială respectă constrângerile fete-băieți bool eValid(int k) { int girls = 0, boys = 0; for (int i = 0; i <= k; i++) { if (students[solution[i]][0] == 'F') girls++; else boys++; } return girls <= 3 && boys <= 3; // Maximum 3 fete și maximum 3 băieți } // Funcție care verifică dacă soluția completă este validă bool eOk(int k) { return k == GROUP_SIZE; // Grupul este complet } // Funcție pentru afișarea unei soluții valide void printSolution() { for (int i = 0; i < GROUP_SIZE; i++) { cout << students[solution[i]] << " "; } cout << endl; } // Funcția de backtracking pentru generarea grupelor void backtrack(int k) { if (eOk(k)) { // Grup complet format printSolution(); return; } for (int i = (k == 0 ? 0 : solution[k - 1] + 1); i < TOTAL; i++) { solution[k] = i; if (eValid(k)) { backtrack(k + 1); } } } int main() { backtrack(0); return 0; }
Leave a Comment