Solução Transporte de Painéis Solares

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.

https://gist.github.com/rogerioagjr/509f8def65ec01217847