Blog do Silveira

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:

1. A soma dos elementos em S seja a maior possível.
2. 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.

A solução para o problema é o melhor deste três casos.
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:

Vamos aplicar o mesmo raciocínio, mas pegando os dois elementos do meio desta vez:

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) = O(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.

Há muitas formas de não calcular isso repetidamente. Uma implementação pequena, em Python , que calcula o valor de S (mas não S) seque a sequir:

A = [12,15,10,4,9,11]

T = []for i in range(len(A)):

 if i==0:

 	T.append(A[0])

 elif i==1:

 	T.append(max(A[0],A[1]))

 elif i==2:

 	T.append(max(A[1],A[0]+A[2]))

 else:

 	T.append(max(A[i]+T[i-2],A[i-1]+T[i-3]))

print max(T[len(A)-1],T[len(A)-2])

A cada passo ele calcula a melhor solução para o vetor que começa de 0 até i+1. No primeiro passo ele calcula a soluçãopara o vetor [12], no segundo passo para o vetor [12,15] e no terceiro passo para o vetor [12,15,10]. Estes três casos sãoos casos bases. As soluções são guardadas no vetor T. Para os demais casos, onde ele faz a seguinte pergunta: Quem é melhor?

• A[i] somado com a melhor solução de A[1..i-2] ou
  A[i-1] somado com a melhor solução de A[1..i-3]

A melhor solução de A[1..i-2] fica armazenada em T[i-2], assim como a melhor solução de A[1..i-3] fica armazenadaem T[i-3].No final, as ultimas duas posições do vetor T guardam a melhor solução, então pegamos a maior delas.

Observações: Não estamos guardando que elementos tomamos para chegar na solução ótima. Para darmos a solução ótima temos que guardar informação extrasobre que caminhos tomamos durante a execução do algoritmo.

Este outro algoritmo, um pouco maior, guarda essa informação num vetor auxiliar C. Quando estamos em T[i] e vemos que T[i]+T[i-2] é o maior
então colocamos verdadeiro em C, o que significa que A[i] foi escolhido na melhor solução de T[i]. Caso contrário, T[i-1]+Ti-3] é maior e então A[i] é quem
está na solução. Neste caso colocamos falso em C[i].
No final do algoritmo percorremos C de trás para frente, refazendo o caminho da melhor solução.

# http://silveira.wordpress.com

# silveiraneto@gmail.com

A = [12,15,10,4,9,11]

T = []

C = []

S = []for i in range(len(A)):

 # Caso base com um elemento

 if i==0:

 	T.append(A[0])

 	C.append(True)

 # Caso base com dois elementos

 elif i==1:

 	if(A[1]>A[0]):

 		T.append(A[0])

 		C.append(True)

 	else:

 		T.append(A[1])

 		C.append(False)

 # Caso base com tres elementos

 elif i==2:

 	if(A[2]+A[0]>A[1]):

 		T.append(A[0]+A[2])

 		C.append(True)

 	else:

 		T.append(A[1])

 		C.append(False)

 # Caso geral

 else:

 	if(A[i]+T[i-2]>A[i-1]+T[i-3]):

 		T.append(A[i]+T[i-2])

 		C.append(True)

 	else:

 		T.append(A[i-1]+T[i-3])

 		C.append(False)

# Descobre se a melhor solucao foi com o ultimo ou com o penuntimo elemento

if(len(A)>=2):

 if(T[len(A)-1]>T[len(A)-2]):

 	i = len(A)-1

 else:

 	i = len(A)-2

if len(A) == 0:

 i = -1

# Percorre o vetor C de tras para frente, se um valor eh verdadeiro entao aquela posicao foi escolhida e pegamos o elemnento de A correspondente e voltamos duas posicoes. Se eh falso entao aquele elemento em A nao foi escolhido e vamos uma posicao para a esquerda.

while i >= 0:

 if(C[i]==True):

 	S.insert(0,A[i])

 	i = i - 2

 else:

 	i = i - 1

print 'A', A

print 'T', T

print 'C', C

print 'S', S