Programação dinâmica [LAB-1]

Problema: Máxima Subsequência Crescente (MSC)¶

** esta atividade é um complemento da aula de mesmo tema

• Entrada: Sequência de $n$ números inteiros: $[a_1,\cdots,a_n]$. Assumimos que $a_0 = -\infty$
• Saída: Subsequência crescente (não necessariamente contígua, mas respeitando ordem) de maior tamanho.

Sejam os subproblemas caracterizados como:

$c(i,j):$ tamanho da MSC dos elementos nas posições $j \cdots n$ com todos os elementos maiores do que $a[i]$

Sendo assim, temos os seguintes índices para as dimensões do problema:

• $i: 0 \cdots n$. Pois consideramos como limite inferior cada um dos elementos da sequência de entrada mais o $-\infty$, que funciona como o pivot.
• $j: 1 \cdots n+1$. Pois crescemos a MSC da direita para a esquerda, sendo $n+1$ representando a sequência vazia.
• Sempre temos que $j > i$, já que só faz sentido existir um limite inferior que esteja à esquerda da sequência de elementos considerados.

A seguinte equação recursiva representa o custo de uma solução ótima para o problema:

$c(i,j) = \begin{cases} 0 & j > n \\ c(i,j+1) & a[j] \leq a[i] \\ \max(c(i,j+1), 1 + c(j,j+1)) & a[j] > a[i] \end{cases}$

Exercício 1: algoritmo de programação dinâmica¶

Você deve construir um programa em C/C++ com nome mscpd.cpp que receba na entrada padrão $n$ inteiros e retorne na saída duas matrizes: (1) matriz que representa os custos das soluções ótimas para os subproblemas; e (2) matriz que permite rastrear/reconstruir as MSCs propriamente ditas.

Exemplo de arquivo de entrada entrada1.txt (mesmo exemplo dado em sala):

7
0 7 3 10 1 5 8

Exemplo de arquivo de saída saida1.txt (mesmo exemplo dado em sala):

7
0 7 3 10 1 5 8
4 3 3 3 3 2 1 0
0 3 3 3 3 2 1 0
0 0 1 1 1 1 1 0
0 0 0 2 2 2 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 2 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0
1 0 0 0 1 1 1 0
0 0 0 0 1 1 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0

Explicação: primeira linha indica o tamanho $n$ do problema, o que consequentemente indica que o tamanho da sequência de entrada. A segunda linha representa a sequência de entrada propriamente dita. As outras linhas representam duas matrizes $(n+1) \times (n+1)$: (1) matriz de custos contendo os custos ótimos das soluções e (2) matriz de soluções, permitindo a reconstrução da solução. Por isso temos um restante de 16 linhas: 8 para cada matriz. Com relação à segunda matriz, 1 indica “seta diagonal” (melhor solução adicional o elemento -- $1 + c(j,j+1)$), 0 indica o contrário, ou “seta direita” ou inexistência de entrada na célula da matriz.

Exercício 2: reconstrução da solução a partir da matriz de soluções¶

Você deve construir um programa em C/C++ com nome mscsol.cpp que receba na entrada padrão a saída do algoritmo implementado no exercício anterior (isto é, as duas matrizes). O programa deve gerar na saída padrão a MSC da sequência completa. Para o exemplo anterior, a saída deve ser (em uma única linha):

0 1 5 8