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  data-recalc-dims= 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.


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 110
#define MAXC 15
#define INF 0x3f3f3f3f
// declaro as variáveis que vou usar
int n, c, f, casos, peso[MAXN], dp[MAXN][MAXC];
// função recursiva para calcular a DP
int maior(int ini, int qtd){
// se já tiver calculado este estado,
// retorno este resultado pré-calculado
if(dp[ini][qtd]>=0) return dp[ini][qtd];
// se qtd for 1, só tenho 1 caminhão
if(qtd==1){
// logo ele será o mais pesado
// e devo retornar a soma de todos os painéis de ini a n
// pois ele levará todos eles
int soma=0;
for(int i=ini; i<=n; i++) soma+=peso[i];
return dp[ini][qtd]=soma;
}
// se tenho mais de um caminhão
int soma=0, menor=INF;
// peercorro todos os painéis
// escolhendo qual será o último levado pelo primeiro caminhão
for(int i=ini; i<=n; i++){
// adiciono a soma seu valor
soma+=peso[i];
// e vejo se o peso do mais pesad é mínimo
menor=min(menor,max(soma,maior(i+1, qtd-1)));
}
// retorno o melhor valor possível
return dp[ini][qtd]=menor;
}
int main(){
// leio a quantidade de casos
scanf("%d", &casos);
// para cada caso
for(int t=1; t<=casos; t++){
// zero a tabela de DP
memset(dp,-1,sizeof(dp));
// leio os valores da entrada
scanf("%d %d %d", &n, &c, &f);
for(int i=1; i<=n; i++) scanf("%d", &peso[i]);
// e imprimo o resultado calculado pela DP
printf("%d $%d\n", maior(1,c), maior(1,c)*c*f);
}
return 0;
}

view raw

paineis.cpp

hosted with ❤ by GitHub