Problema retirado do teste 5 do professor Carlos.
Considere um vetor A[1..n] de números positivos. O problema consiste em encontrar um subconjunto S de elementos de A tal que:
-
A soma dos elementos em S seja a maior possível.
- S não contenha dois elementos consecutivos de A.
Exemplo: A solução deste problema para o vetor A = <12,15,10,4,9,11> é o conjunto S = {12,10,11}. Note que o maior elemento de A não aparece na solução.
Construir um algoritmo para encontrar um S ótimo.
Solução 1:
Suponha que temos um vetor V, vamos analisar a parte do meio do vetor. Mais precisamente os dois elementos do meio do vetor
Desses 3 elementos do meio, pelo menos um deles vai estar na solução (isso vale para qualquer 3 elementos consecutivos).
Vamos analisar estes 3 casos:
Caso 1) Se o primeiro desses elementos do meio está na solução:
Então vamos pegar a solução ótima da esquerda e da direita e concatenar com o elemento do meio.
Caso 2) Se o segundo elemento do meio está na solução:
Novamente pegamos a solução ótima da esquerda e da direita e concatenamos com o elemento do meio.
Caso 3) Se o terceiro elemento do meio está na soluçao:
Mais uma vez vamos pegar a solução da esquerda e da direita e concatenar com o elemento do meio.
O caso base para este algoritmo pode ser com um vetor de tamanho até k. Nesse caso fazemos uma força bruta, ou seja, olhamos para todas as possibilidades. Podemos fazer este K bem pequeno, 2 ou 3.
Análisando a complexidade deste algoritmo temos:
T(n) = O(1) + 6 * T(n-3/2)
Ou seja, para um vetor de tamanho n vamos olhar seis casos, para cada um dos 3 casos vamos olhar para a esquerda ou para a direita. O tamanho desse vetor da direita ou da esquerda é n-3/2 ou seja, o vetor original subtraido de três elementos e dividido por 2.
T(n) vai ficar O(n³)!
Solução 2:
Nos dois elementos do meio, temos 3 possibilidades: ou nenhum dos dois vão participar da solução ótima, ou o primeior vai participar da solução ótima ou o segundo vai participar da solução ótima. Vamos análisar estas possibilidades:
Caso 1) Se nenhum dos dois está na solução. Isso aconteceu porque os dois elementos vizinhos do meio estão na solução ótima.
Então o que fazemos é ignorar os elementos do meio e calcular a solução ótima para a esquerda e para a direita.
Caso 2)
Se o primeiro elemento do meio está na solução ótima.
Então, fazemos a mesma coisa. Pegamos a melhor solução da esquerda e da direita e concatenamos com o elemento do meio.
Note que a solução da parte direita já foi feita no caso 1.
Caso 3)
Se o segundo elemento do meio está na solução ótima.
Novamente, pegamos a solução da esquerda e da direita e concatenamos com o elemento do meio.
Note que a parte da esquerda já foi resolvida no caso 0.
A solução para o problema, é o melhor desses três casos. O caso base vai ser um vetor de tamanho k, onde aplicaremos uma força bruta. Esse k pode ser bem pequeno, 1, 2 ou 3.
Análisando a complexidade desse algoritmo temos:
T(n) = O(1) + 4*T(n-2/2)
Isto é, o custo da concatenação, que é um custo constante. O custo de análisar os mesmos problemas que tem mais ou menos metade do tamano original do problema menos dois elementos.
Desenvolvendo chegamos a T(n) = n².
Solução 3)
Vamos utilzar agora uma outra abordagem.
Se olharmos para os dois primeiros elementos do vetor podemos observar que
ou o primeiro elemento vai participar da solução ótima
ou o segundo elemento vai participar da solução ótima (obs:podemos provar isso por contradição).
Vamos análisar como resolver os dois casos:
Caso 1)
Se o primeiro está na solução ótima, então a melhor solução é o primeiro elemento concatenado com a solução ótima da direita pulando seu vizinho.
Caso 2)
Se o segundo é quem está na solução ótima, então a melhor solução é o segundo elemento concatenado com a solução ótima da direita pulando seu vizinho.
Então, a solução ótima para um entrada de tamanho n é a melhor das soluções entre o caso 1 e o caso 2, ou seja, a de maior soma dos seus elementos. O caso base é uma entrada de tamanho k, onde é feito a força bruta para achar a solução ótima. Esse k pode ser bem pequeno, 1, 2 ou 3.
O tempo gasto para se executar uma entrada n é dado pela expressão:
T(n)=O(1)+T(n-2)+T(T-3)
O(1) é o tempo de concatenar um elemento para forma a solução e o tempo para comparar as duas soluções. T(n-2) é o tempo para resolver o caso 1 e t(n-3) é o tempo para resolver o caso 2, respectivamente, o tempo para calcular o melhor caso sobre uma entrada de tamanho n retirado 2 elementos e o mesmo retirado 3 elementos.
Se desenvolvermos a expressão T(n) por iteração, obtemos:
T(n)=O(1)+T(n-2)+T(T-3)
T(n)=O(1)+O(1)+T(n-4)+T(n-5)+T(T-3)+O(1)+T(n-5)+T(n-6)
T(n)=3*O(1)+T(n-4)+2*T(n-5)+T(n-6)
T(n)=3*O(1)+O(1)+O(n-6)+T(n-7)+2*(O(1)+T(n-7)+T(n-8))+O(1)+T(n-8)+T(n-9)
T(n)=7*O(1)+T(n-6)+3*T(n-7)+3*T(n-8)+T(n-9)
A cada iteração, cada termo T vira outros dois termos T.
No primeiro nível, temos um elemento, no segundo o dobro, no terceiro o dobro do dobro. Ou seja, cada nível possui 2^n termos T. Ou seja, isso cresce exponencialmente.
T(n)=O(2^n). O que é muito pior do que qualquer outra solução vista até agora.
Solução 4)
Na solução 3, que é de ordem de 2^n, o crescimenento exponencial se dá porque a cada iteração o problema se divide em outros dois de quase o mesmo tamanho do original. Mas reparamos mais cuidadosamente na árvore que mostra o crescimento de T(n):
Aqui colorimos os termos de modo que termos iguais tenham a mesma cor. Observe que T(n-8) é calculado 3 vezes e T(n-7) também. Se continuarmos a expandir essa árvore encontrariamos cada vez mais elementos repetidos.
Se encontrarmos uma forma de não calcular esses termos repetidos, conseguiriamos decrescer drásticamente a ordem de magnitude do algoritmo. É um problema muito semelhante ao encontrado no cálculo da sequência de Fibonacci.
Vamos utilizar um vetor auxiliar T de tamanho n, inicialmente inicializado com suas posições zeradas. Um termo i do vetor T correspoderá a T(n-i). Ou seja, o segundo termo de T denota T(n-2).
O RESTO ESCREVO DEPOIS... :)