Bonjour a tous , 

Je dois effectuer un BackTracking dans le cadre de l'exercice suivant : 

Nous cherchons a creer une coalition de partis politiques avec le maximum de mandats possibles 

Je possède un tableau de booléen can_collaborate[N][N] qui me permet de savoir qui veut etre dans la coalition , un tableau mandates[N] qui nous donne le nombre de mandat par parti politique.

Mon BackTracking marche mais ne fait pas tout les cas possibles ( me renvoie une coalition possible mais pas la plus grande possible )

int max_coalition(int mandates[], bool can_collaborate[][N],
                  int max_parties[N])
{
    bool chosen[N] ;
    for (int i=0;i<N;i++)
        chosen[i]=false;
    for (int i=0;i<N;i++)
        max_parties[i]=-1;


    int sum_to_check = 60;
    max_coalition_aux (mandates,can_collaborate,max_parties,chosen,0,&sum_to_check);

    return countParties(chosen);
}


bool max_coalition_aux (int mandates[], bool can_collaborate[][N],
                       int max_parties[N],bool chosen[N],int current,int *sum) {


    if (current == N)
        return IsLegalCoallition(mandates, can_collaborate, chosen);

    int highestIdOpened = 0;
    for (int i = 0; i < current; ++i)
        highestIdOpened = max(highestIdOpened, max_parties[i]);

    int partiId;
    for (partiId = 0; partiId <= highestIdOpened + 1; ++partiId) {

        if (chosen[partiId] != false)
            continue;

        if (isLegalPlacement(can_collaborate, chosen, current)) {

            chosen[partiId] = true;

            max_parties[current] = partiId;

            if (max_coalition_aux(mandates, can_collaborate, max_parties,
                                  chosen, current + 1, sum) == true) {
                placeParties(chosen, max_parties, mandates, sum);
                return true;
            }
        }
        chosen[partiId] = false;
        max_parties[current] = -1;
    }
    return max_coalition_aux(mandates, can_collaborate, max_parties,
                             chosen, current + 1, sum);
}

Exemple : Dans le cas 

20 14 30 16 40
1 1 1 0 1
1 1 1 1 1
1 1 1 1 0
0 1 1 1 1
1 1 0 1 1 

je devrais recevoir {0,1,4} mais je reçois {0,1,2}

Faut déboguer - essaie de trouver un exemple minimal qui te permet de trouver le problème. C'est à dire, un exemple que tu peux facilement faire à la main - et tu vérifies avec des print et/ou débogueur que tout se passe comme tu veux dans l'implémentation de ton algorithme.

oui justement jai essaye de debuger apres avoir trouve le {0,1,2} il s'arrete considérant avoir trouve la configuration requise

BellahsenRaphael a écrit:

oui justement jai essaye de debuger apres avoir trouve le {0,1,2} il s'arrete considérant avoir trouve la configuration requise

Du coup tu as déjà une piste pour chercher ! Tu n'as plus qu'à chercher maintenant pourquoi il "pense avoir trouvé la configuration requise"

Met des printf dans les fonctions adéquates, et cherche à savoir pourquoi il s'arrête, puis une fois que tu sais pourquoi il s'arrête, remonte progressivement jusqu'à trouver la vraie raison.

-
Edité par potterman28wxcv 21 juin 2019 à 13:17:51