Solução Transporte de Painéis Solares

0 Flares Facebook 0 0 Flares ×

Solução de Rogério Júnior

Clique aqui para ver o problema original

Se, para um determinado transporte, usei n caminhões, o maior peso transportado foi x e o valor do frete era f, o preço será n \times x \times f.

Abordaremos este problema usando programação dinâmica, pela simplicidade do código. O estado da DP será constituído de dois inteiros: ini e qtd, e usaremos a função recursiva maior para calcular seu valor. Deste modo, a função maior(ini,qtd) deve retornar a resposta para a seguinte pergunta: dentre todas as possíveis maneiras de dividirmos os painéis solares a partir do índice ini entre qtd caminhões, qual o peso do caminhão mais pesado na maneira de carregar os painéis em que o peso deste caminhão (mais pesado) é o menor possível?

A base da DP é muito simples: se só temos um caminhão (qtd = 1), então ele transportará todos os painéis a partir do de índice ini, sendo portanto o mais pesado (por ser o único) e devemos retornar a soam de todos os painéis a partir do de índice ini.

Vejamos agora a fórmula geral da DP. se qtd > 1, vamos decidir que painéis colocaremos no primeiro caminhão. Para cada índice i \geq n, veremos qual seria o peso do caminhão mais pesado se o primeiro caminhão levasse os painéis de ini a i. Guardaremos em soma o peso que este primeiro caminhão está levando e a função maior(i+1, qtd-1) retornará o peso do mais pesado entre os outros caminhões na configuração ótima. Assim, o peso do caminhão mais pesado (se o primeiro levar os painéis de ini a i) será o maior dentre soma e  maior(i+1, qtd-1). Basta calcularmos este valor para cada i (ou seja, todos os valores de modo que ini \leq i \leq n, se indexarmos cada painel de 1 a n e retornar o menor deles.

Agora que a função maior já está implementada, sabemos que o menor valor possível para o maior peso transportado pelos c caminhões na tentativa de transportar os painéis de 1 a n é maior(1,c), logo devemos imprimir "maior(1,c) $maior(1,c)*c*f", onde f é o valor do frete. Segue o código comentado para melhor entendimento.

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: