Introdução à Programação Dinâmica

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. . .