Programação dinâmica é uma técnica de resolução de problemas que aparece de muitas formas em várias situações. A programação dinâmica é baseada na aplicação da técnica de divisão e conquista nos problemas nos quais os subproblemas gerados se repetem. Esta propriedade chamamos de sobreposição de subproblemas.
Nem sempre é fácil dividir o problema e encontrar os problemas sobrepostos.
Problema do Tijolo
Nós queremos construir uma parede de tijolos com tijolos do tipo 2 x 1, e se o nosso muro deve ter de duas unidades de altura, podemos fazer o nosso muro de várias maneiras, dependendo do comprimento do muro.
De quantas maneiras podemos construir um muro com comprimento 4? E comprimento 5? Precisamos aplicar a técnica de divisão e conquista para resolver este problema. Primeiramente, podemos observar que o tijolo pode ficar em pé ou dois deitados.
Considerando uma parede inicial com comprimento n, no primeiro caso, temos que cobrir uma parede com comprimento n-1 e no segundo caso uma parede com comprimento n-2.
Se observamos a maneira que uma parede com comprimento 3 é coberta, podemos notar que as duas primeiras maneiras começam com um tijolo em pé depois segue o padrão do comprimento 2 e a última maneira começa com dois tijolos deitados.
Algoritmo
int f(int n){
cont++;
if(n<=2) return n;
else return f(n-1)+f(n-2);
}
int main(){
cont = 0;
clock_t begin = clock();
printf("%d\n",f(40));
printf("chamadas %d\n",cont);
double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);
}
165580141
chamadas 204668309
EXECUTION TIME(seconds): 1.367 second(s).
Observe que existe muita intersecção entre os subproblemas gerados.
f(5)
f(4) + f(3)
f(3)+f(2) + f(2) + f(1)
f(2)+f(1)+ f(2) + f(2) + f(1)
Por exemplo, para resolver f(5) será resolvido uma vez f(4), duas vezes f(3), três vezes f(2) e duas vezes f(1).
Podemos reduzir o número de chamadas aproveitando a própria estrutura recursiva e construindo uma solução bottom-up (de baixo para cima).
int f2(int n){
int f[n+1];
int i;
if(n<=2) return n;
else{
f[1] = 1;
f[2] = 2;
for(i=3;i<=n;i++){
f[i] = f[i-1]+f[i-2];
}
return f[n];
}
}
165580141
EXECUTION TIME(seconds): 0.001 second(s).
Uma técnica que pode ser utilizada para reduzir o número de chamadas desnecessárias é a memorização. A memorização consiste em guardar os valores computados para que eles não precisem ser computados novamente.
int memo[MAXN];
void init(){
int i;
for(i=0;i<MAXN;i++) memo[i] = -1;
memo[1] = 1;
memo[2] = 2;
}
int f3(int n){
cont++;
if( n <= MAXN ){
if(memo[n]!=-1) return memo[n];
else{
memo[n] = f3(n-1) + f3(n-2);
return memo[n];
}
}else{
return f3(n-1) + f3(n-2);
}
}
int main(){
cont = 0;
clock_t begin = clock();
init();
printf("%d\n",f3(40));
printf("chamadas %d\n",cont);
double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);
}
165580141
chamadas 77
EXECUTION TIME(seconds): 0 second(s).
Número de combinações
O número de combinações pode ser obtido pela seguinte fórmula:
C(n,k) = $\frac{n!}{k!(n-k)!}$
C(n,k) representa o número de subconjuntos de tamanho k que podem ser formados a partir de um conjunto com n elementos. Observe que podemos dividir em subproblemas fazendo uma simples observação.
Escolha um elemento x qualquer do conjunto com n elementos. O elemento x pode está ou não no subconjunto com k elementos formados.
Caso 1: x está no subconjunto que está sendo formado. Precisamos escolher k-1 elementos de conjunto com n-1 elementos.
Caso 2: x não está no subconjunto que está sendo formado. Precisamos escolher k elementos de conjunto com n-1 elementos.
C(n,k) = C(n-1,k-1) + C(n-1,k)
int C(int n, int k){
cont ++;
if(k==0 || n==k ) return 1;
else return C(n-1,k-1) + C(n-1,k);
}
int main(){
cont = 0;
clock_t begin = clock();
printf("%d\n",C(30,10) );
printf("chamadas %d\n",cont);
double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);
}
30045015
chamadas 60090029
EXECUTION TIME(seconds): 0.48 second(s).
Pressione qualquer tecla para continuar. . .
Memorizando
int memo[MAXN][MAXN];
void init(){
int i,j;
for(i=0;i<MAXN;i++)
for(j=0;j<=i;j++)
memo[i][j] = -1;
for(i=0;i<MAXN;i++)
memo[i][0] = memo[i][i] = 1;
}
int C(int n, int k){
cont ++;
printf("%d %d\n",n,k);
if(memo[n][k]!=-1) return memo[n][k];
else {
memo[n][k] = C(n-1,k-1) + C(n-1,k);
return memo[n][k];
}
}
int main(){
cont = 0;
clock_t begin = clock();
init();
printf("%d\n",C(30,10) );
printf("chamadas %d\n",cont);
double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);
system("PAUSE");
}
30045015
chamadas 401
EXECUTION TIME(seconds): 0.001 second(s).
Pressione qualquer tecla para continuar. . .
