Problema D

Autor: Hugo Vieira (Faculdade de Ciências da Universidade de Lisboa)
Tipo de problema: Programação Dinâmica
Número de ficheiros de teste: 13

Tesar todas as combinações possíveis de carros nos barcos está fora de hipótese (não passa no tempo).

Uma solução greedy também não passa, porque a decisão "actual" vai influenciar decisões futuras (não temos informação suficiente para decidir sem saber o que vai estar no resto dos barcos):

Problemas onde é necessário optimizar algo (máximos/mínimos) ou contar algo, e onde a solução "bruta" é exponencial, podem muitas vezes ser resolvidos com programação dinâmica (PD).

Vamos então aplicar PD a este problema. O "complicado" é arranjar uma formulação do problema que caiba no âmbito de PD. Consideremos o seguinte (existiam outras maneiras de fazer):

best[i] = supondo que o carro i é o último do seu barco,
          o mínimo de espaco a desperdicar para colocar todos
          os carros desde o primeiro até i

Como os carros estão sempre na mesma sequência, se C for o número de carros, a solução será o valor de best[C].

E como calcular os vários valores de best[]?

best[i] = min, para os j < i, de:
          best[j-1] + espaço_livre(melhor barco carros de i a j)

Nota que o melhor barco para um conjunto de carros deve ser o mais pequeno onde caibam todos. Qualquer barco maior deixa livre mais espaço e qualquer barco menor não consegue levar todos os carros.

Para calcular o melhor barco, podemos começar por ordenar os barcos e depois à medida que vamos descendo o j para cada cálculo de best[i] podemos ir também "subindo" na lista dos barcos.

Este algoritmo pode parecer quadrático no número de carros (que era 100,000) mas no entanto, reparemos que num barco só cabem no máximo 20 carros (tamanho máximo de um barco é 1000 e tamanho mínimo de carro é 50). Logo, cada best[i] demorará no máximo 100 (num. barcos) + 20 (num. carros), pois quando os carros já não cabem no maior barco, já não vale a pena continuar.

Ligações interessantes:

Problema D - Ferry Boats