backtracking

 avatar
user_2044853
c_cpp
13 days ago
1.4 kB
3
Indexable
#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