Desafio: maximizar afinidades

Numa escola, antes da definição das turmas, cada aluno preenche um formulário informando com quais colegas tem afinidade, resultando na tabela abaixo (onde 1 indica afinidade).

Matriz de afinidades (é simétrica, se um aluno tem afinidade com outro, o inverso também é verdadeiro):

A escola deve dividir os 15 alunos em 3 turmas de 5 alunos cada.Dois alunos com afinidade gostam de estar na mesma turma, e dois alunos sem afinidade são indiferentes.

O score de afinidade total é calculado assim: para cada turma, cada par de alunos com afinidade acrescenta 1 ao score.

Exemplo. Se uma turma tem os alunos 1, 2 e 3, o score de afinidade para esta turma será 1:

- Aluno 1 afim com Aluno 2: 1

- Aluno 1 não afim com Aluno 3: 0
- Aluno 2 não afim com Aluno 3: 0

Qual a melhor forma de alocar os alunos, de modo a maximizar a afinidade total?

Posto respostas até segunda da semana que vem.

Veja também:

Originally published at https://ideiasesquecidas.com on May 20, 2023.