Introdução a ciencias da computação

Otimizando o Trem Bala
O trem bala vai ser construído ligando Rio-São José dos Campos-São Paulo-Campinas-Americana-São Carlos

Faça um simulador para avaliar a movimentação de passageiros do trem-bala. Nós queremos otimizar o uso dos trens, usando o mínimo de vagões para transportar o máximo de clientes e obter o máximo de lucro.

Levando em conta que:

Custa R$ 25 000.00 para levar cada vagão de São Carlos até o Rio e de volta.
Não é possível mudar o número de vagões durante uma viagem de ida e volta.
Cada viagem começa e termina em São Carlos.
Cada vagão pode levar até 150 pessoas.
Cada cliente paga R$ 50.00 por trecho viajado.
Se um cliente não consegue embarcar, pagamos a ele R$ 200.00 por trecho comprado.
Se houver espaço no trem, todos os passageiros esperando embarcam.
Se não houver espaço para todos (dica: a segunda opção é mais fácil de implementar):
Escolhemos aleatoriamente quem embarca (simulamos que quem chegou primeiro embarca) OU
As pessoas que vão para as estações mais próximas não embarcam. Ex: Ao chegar o trem na estação B e desembarcarem os passageiros para essa estação sobram 1000 lugares no trem. Na estação B existem 200 pessoas que vão para a estação C, 600 pessoas que vão para a estação D, 600 pessoas que vão para a estação E. Nesse exemplo não seriam embarcados os 200 passageiros que vão para a estação C e 200 dos 600 passageiros que vão para a estação D.
Cada cidade tem uma estação, num total de 5 trechos.
Em cada parada irão embarcar um certo número de passageiros e desembarcar outra quantidade de passageiros (controlados pelas catracas eletrônicas), podendo restar um certo número de passageiros a bordo.

O programa recebe 10 matrizes, como a abaixo, com o número de passageiros para cada viagem de ida e volta. Cada linha representa uma estação de embarque e cada coluna um destino a partir dessa estação (Ex: na ida - embarcaram 100 pessoas em São Carlos para Americana, na volta: embarcaram 45 pessoas em Americana para