Questão de maratona de programação

Programação Java
#1

Galera, participei de uma maratona, classificamos, mas o problema é que fiquei puto com essa ques tão, não consegui resolver, foi a unica que não consegui. --’
poderiam me ajudar com a logica na comparação ? como saber os numeros dos músicos…

4 Questão: Banda Beatle4Ever

George Harrison é um garoto muito esperto que adora música. No último mês ele ganhou um campeonato cujo objetivo era tocar guitarra alucinadamente. Empolgado, George decidiu montar uma banda. Para ele a banda perfeita tem quatro integrantes, ele e mais três: um baterista, um baixista e um cantor. Agora George precisa encontrar os outros integrantes da banda. Para isto ele reuniu todos os álbuns que encontoru na internet e, após escutá-los diversas vezes, compilou o que ele chama de lista de entrosamento entre músicos. Nessa lista ele atribui, para cada par de músicos tocam juntos, uma nota inteira de 1 a 100, que é uma medida de quão bem os músicos tocam juntos (conhecido como o nível de entrosamento entre eles). Se dois músicos nunca tocaram juntos o nível de entrosamento é zero. Georde nunca tocou com nenhum músico da lista e pretende formar sua banda a partior da lista de entrosamento entre músicos, da seguinte maneira: ele quer escolher os outros três músicos de tal forma que a soma dos níveis de entrosamento dos integrantes da banda seja a maior possível (ou seja, a soma dos níveis de entrosamento dos três pares possiveis de serem formados entre os três novos integrantes seja a maior possível). Mas a lista de entrosamento entre músicos ficou muito grande e George não está conseguindo escolher os integrantes. Por isso, George está pedindo sua ajuda.

TAREFA
Você de ve ajudar Jimmy a montar a melhor banda possível fazendo um programa que receba uma lista contendo o nível de entrosamento para cada par de m úsicos que já tocaram juntos, e determine os músicos que formariam a melhor banda.

ENTRADA
A entrada contem um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada e formada por dois inteiros N e M, informando respectivamente o número de músicos e o número de pares de músicos que já tocaram juntos . Os músicos são identificados por números inteiros de 1 a N . Cada uma das M linhas seguintes contem treês inteiros X, Y e Z, em que x e y representa um par de músicos e Z representa o seu nível d e entrosamento. Cada par de músicos que já tocou junto aparece uma única vez na entrada.

SAÍDA
Seu programa deve imprimir, na saída padrão, uma única linha, contendo três números inteiros separados por espaço em b ranco, identificando os três outros músicos que devem compor a banda (em qualquer ondem). Se existir mais de uma melhor banda, Jimmy contenta-se com qualquer uma

ENTRADA | SAIDA (Exemplo para mostrar o que tem que entrar e o que tem que sair)
3 3 | 1 2 3
1 2 50 |
2 3 27 |
3 1 1 |

Tive uma dificuldade danada nesse programa, se alguém que tenha entendido me explicar como resolveu, só não consegui comparar, peguei as notas, peguei o número do músico, só não consegui achar qual era a melhor banda mesmo, tomara que consigam me ajudar.
abraço.

#2

Tem uma coisa esquisita nesse problema. Ele estipulou qual era o N máximo?

#3

Se N for 10, usando uma forma estúpida de achar todas as relações entre N músicos 3 a 3, teremos:

N! 3!
(N-3)!

que dá 6 N (N-1) (N-2). Por exemplo, se tivermos 10 músicos, teremos 4320 combinações.

#4

então, ele vai dar o número de combiações possiveis, então:

System.out.prinln("entre com o número de músicos");
musicos = entrada.nextInt();

System.out.prinln("entre com o número de duplas");
comb = entrada.nextInt();

for (int i=0; i<comb; i++)
{
     System.out.prinln("entre com o número de músicos");
     mus1 = entrada.nextInt();

     System.out.prinln("entre com o número de duplas");
     mus2 = entrada.nextInt();

     System.out.prinln("entre com a nota do entrosamento");
     entros = entrada.nextInt();

     nota[i] = entros;
}

não fiz isso na hora, ficou bem melhor, mas é mais ou menos assim entende? ele vai entrar com o número dos 2 musicos e dar uma nota para esses dois juntos.
Exemplo:
musico 1 e 2 tiveram a nota pelo entrosamento 50
musico 1 e 3 tiveram a nota pelo entrosamento 50
musico 1 e 4 tiveram a nota pelo entrosamento 50
musico 2 e 3 tiveram a nota pelo entrosamento 10
musico 4 e 3 tiveram a nota pelo entrosamento 60
musico 2 e 4 tiveram a nota pelo entrosamento 30

ai eu teria que saber quais seriam os 3 musicos selecionados por melhor entrosamento, entendeu?
no caso, os escolhidos seriam: musico 1, 3 e 4.

consegui guardar o número do musico e o entrosamento, mas depois nao consegue comparar e mostrar quais seriam tiveram melhor resultados juntos.
escrevi o problema exatamento como a folha descreve.

#5

Uma forma estúpida de resolver esse problema é a seguinte: gere todas as combinações de N músicos 3 a 3 (sem repetição).

Para gerar todas as combinações (não permutações) possíveis, procure na Internet os algoritmos.

Então ache a soma dos relacionamentos para cada combinação (como guardar os relacionamentos de forma eficiente, fica por sua conta), e guarde em uma variável separada os 3 músicos e sua soma de relacionamentos se ela for maior que a soma dos relacionamentos dos músicos correntes.

Por exemplo, digamos que você tenha descoberto que 1, 2 e 3 dão a seguinte soma de relacionamentos: 20
Se 1, 2, 4 der uma soma 18, você não precisa guardar, mas se 1, 3, 4 der a soma 21, então você agora guarda o valor 21 (que é a soma) e os músicos 1, 3, 4 (que dão a maior soma até a combinação corrente.

#6