CD

Neste problema, devemos analisar todas as combinações de músicas possíveis para ver qual delas deixa menos espaço livre na fita. Sendo assim, parece um problema muito adequado para backtracking.

Para representar o problema, podemos utilizar um array de inteiros para guardar a duração e cada música e um bit array para saber se durante aquela expansão do backtracking uma determinada música foi ou não escolhida. Como o tamanho limita o número de músicas a 20, achei mais simples declarar os arrays com tamanho fixo de 20 e ter uma variável para saber até onde iremos nesse array.

Sendo assim, por exemplo, a entrada "5 3 1 3 4" seria representada:

Array de duração:

E o bit array da solução estaria inicialmente vazio, ou seja, não escolhemos a solução ainda:

A função para encontrar os candidatos, deve escolher somente as músicas que ainda não foram escolhidas e também deve podar para evitar escolher uma música que ultrapassaria o limite. Se lembre, só retorne candidatos válidos.

Na sua função de processar solução, lembre-se que você deve ficar somente com a melhor solução. E se você encontrar uma solução exata, pode parar a execução.

Além disso, ainda tem mais uma poda que você pode fazer na função de encontrar os candidatos, mas essa eu deixo pra você descobrir :-)