Embora nosso algoritmo encontre o valor da solução ótima, ele não obtém a solução em si.

Uma opção é modificar o algoritmo para que ele armazene a solução que está construíndo.

 - Mas isso não costuma ser eficiente em questão de memória. Especialmente em algoritmos de maior dimensão.

Por isso, em geral, o mais eficiente é reconstruir a solução fazendo engenharia reversa no vetor de soluções.

Para tanto vamos olhar novamente para nossa recorrência:

 - A[n] = max{A[n-1], A[n-2] + w[vn]}

E observar que

 - um vértice vi está na solução para Gi se somente se w[vi] + custo da solução para Gi-2 >= custo da solução para Gi-1



Assim, vamos percorrer o vetor do fim para o início

E, em cada posição verificamos qual foi a escolha que o algoritmo fez (usando a recorrência)

 - adicionamos o vértice à solução (se for o caso)
 
 - e avançamos no vetor (em direção ao início)

Para ficar mais claro, considere o seguinte pseudocódigo

 - supondo que o vetor A foi preenchido pelo algoritmo conjInd
 
recSol(G, w, A){
	S = \emptyset
	i = n
	
	enquanto i >= 1
		se A[i-1] >= A[i-2] + w[vi]
			i = i - 1
		senão
			Adicione vi em S
			i = i - 2
	
	devolva S
}

Corretude: pra variar por indução.

Eficiência: O(n).