Jump to content

DP / LIS


Localhost
 Share

Recommended Posts

Bem, voltei a Programação Dinâmica e até já percebi a ideia por detrás desta técnica.

Estive a tentar aplicar o que aprendi no problema clássico (segundo o que li) chamado LIS.

Vou deixar aqui o código e agradecia algum feedback sobre o mesmo:

#include <cstdio>

const int MAX = 1000;

int BottomUp( int *set, int n ) {
   int memo[ MAX ];
        
   for( int i = 0; i < MAX; i++ ) memo[ i ] = 0;
      
   for( int i = 0; i < n; i++ ) {
      for( int j = i + 1; j < n; j++ ) {
         if( set[ i ] < set[ j ] ) memo[ j ] = memo[ i ] + 1;
      } 
   }
        
   return memo[ n - 1 ];
}

int main() {
   int set[ MAX ];
   int n = 0;
        
   scanf( "%i", &n );
   for( int i = 0; i < n; i++ ) scanf( "%i %i", &set[ i ], &set[ i + 1 ] );
      
   printf( "Solution: %i\n", BottomUp( set,n ) );
        
   return 0;
}

p.s. Usei espaços a torto e a direito no código.  🙂

here since 2009

Link to comment
Share on other sites

Já agora deixo aqui um post com o que eu percebi de como usar DP neste problema em particular.

A ideia base é: se temos um elemento i que se encontra numa posição menor que um elemento j e se i < j e se temos ainda um elemento p em que j < p então podemos automaticamente assumir que i < p porque i < j < p. A partir disto podemos assumir que já temos uma subsequence de tamanho 3 (elementos i,j e p).

Vamos então construindo isto sempre com esta pequena lógica em mente.. Começamos num elemento i e verificámos todos os que são maiores que ele no set, assim, todos os que forem maiores já podem pertencer a uma subsequence de tamanho 2 (imaginando que estamos na primeira iteração). Depois vamos para outro elemento, verificámos todos os que são menores, imaginando que este elemento é o j. Se p > j então i < p, ou seja, já temos uma subsequence de tamanho 3. Fazemos isto sucessivamente até chegarmos ao último elemento..

É esta a ideia?

edit: esqueci-me de referir que a ideia de bottom up está claramente presente aqui visto que vamos construindo a solução baseando respostas para estados maiores em respostas em estados menores..

here since 2009

Link to comment
Share on other sites

Em relação ao código, porque usas o %i? O mais corrente usar para ler inteiros é o %d. O %i é para ler o número como hexadecimal ou octal (base 8) caso tenham respectivamente 0x ou 0 no início. Espreita http://en.wikipedia.org/wiki/Scanf

Na leitura, supostamente tens 'n' números, mas lês '2*n' números? E vais escrevendo por cima dos anteriores (vê bem o que escreveste no código)?

Assumindo que a leitura fica correcta, o teu algoritmo mesmo assim está incorrecto.

A tua explicação está um pouco confusa e se calhar, na minha opinião, não cimenta bem o conceito que deves assegurar para re-utilizar as ideias de PD. Pensa no teu memo[] de maneira diferente. Pensa em memo[ i ] como a melhor sequência possível a partir da posição i. Assim, se set[ i ]<set[ j ], então podemos construir a sequência começando pelo elemento set[ i ] e depois continuar com a melhor que começa a partir da posição j. E essa deve ser a alternativa, com tamanho 1+memo[ j ] portanto, deve ser seguida se melhora o valor actual de memo[ i ].

Espreita esta explicação para ver se percebes melhor a ideia do LIS: http://people.csail.mit.edu/bdean/6.046/dp/ (tem explicação oral e tudo)

Link to comment
Share on other sites

Quanto ao scanf foi um vicio que apanhei mas que com certeza será simples de corrigir.

Em relação ao input está a ler assim porque criei este algoritmo para um problema específico, em que o input era feito ao pares.

Em relação à explicação, penso que a sua explicação é igual à minha.. Ou seja, imaginando que i = 0 e j = 1, se set[ i ] < set[ j ] então já temos uma subsequence de tamanho 1, então memo[ j ] = memo[ i ] + 1, ou seja, memo[ j ] = 1 (ou 2, considerando que memo[ 0 ] == 1). Imaginando agora que i = 1 e que j = 2 e que set[ i ] < set[ j ] então já temos uma sequência de tamanho 2 porque podemos assumir que se set[ 0 ] < set[ 1 ] && set[ 2 ] > set[ 1 ] então set[ 0 ] < set[ 1 ] < set[ 2 ]. Aqui memo[ j ] ou memo[ 2 ] = memo[ i ] + 1 ou memo[ 1 ] + 1. Fazemos isto sucessivamente até encontrarmos a solução para o problema. Penso que a solução vai estar sempre em memo[ n - 1 ], não tenho a certeza..

Resumindo: encontrámos o tamanho da maior subsequence a acabar em j ou a começar em i e depois encontrámos a maior subsequence a começar em  j ou a acabar num hipotético p. Correcto?

Edit: Acabei de perceber que afinal a resposta não vai estar em memo[ n - 1 ] mas que pode estar em qualquer lugar de memo[], tem de percorrer memo[] e identificar o maior valor..

here since 2009

Link to comment
Share on other sites

Já tinha visto qualquer coisa sobre como reduzir para O(n log n) mas o meu objectivo não é resolver o problema mas sim resolver o problema usando programação dinâmica para praticar esta técnica. Anyway, obrigado pela informação útil.

here since 2009

Link to comment
Share on other sites

Prof. Pedro Ribeiro, já agora, podia-me dar feedback sobre este código?

#include <cstdio>

const int MAX = 1000;
int set[MAX],best[MAX],n;

void input() {
     scanf("%i",&n);
     for( int i = 0;i < n; i++ ) scanf("%i",&set[i]);
}

int lis() {
     int aux = -1;
      
     for( int k = 0; k < n; k++ ) best[k] = 1;
        
     for( int j = 0; j < n; j++ ) {
        for( int i = j+1; i < n; i++ )
            if( set[j] < set[i] && best[j]+1 > best[i] ) best[i] = best[j]+1;
     }
        
     for( int i = 0; i < n; i++ ) if( best[i] > aux ) aux = best[i];
     return aux;
}

int main() {
     input();
     printf("Answer: %i\n", lis());
     return 0;
}

here since 2009

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.