Algoritmos de programação dinâmica em Javascript

Procurar soluções de projeto de algoritmos que possam ser processados do lado client, principalmente para compilar grandes quantidade de dados de forma eficiente utilizando poucos recursos, hoje em dia é um desafio para os desenvolvedores. Existem muitos conceitos que podem ser aplicados, sendo um deles o conceito de programação dinâmica.

Esse conceito de projeto segue a ideia de pegar um problema “grande” e dividir ele em partes menores, muitas vezes podemos resolver ele com uma função recursiva, mas como grandes partes dos algoritmos recursivos, temos o problema de empilhar varias funções e sobrecarregar a memorias da maquina, no nosso caso dependendo do numero de funções recursivas abertas, o browser travaria.

Agora vamos imaginar que ao invés de encher a memoria com varias funções, usaremos apenas um vetor como apoio para poder processar e cachear os resultados de cada conjunto gerado para resolver o problema, sendo que o tempo e recursos estimados para o processamento esta sempre vinculado ao tamanho do vetor que vamos percorrer, lembrando que com isso temos a vantagem de poder dividir ainda mais o problemas em vetores menores e processar ele conforme as ações do usuários.

Existem um problema computacional bem conhecido que pode ser resolvido através dessa estrategia, o problema de “soma de subconjuntos” ou “exact subset-sum”. Vamos imaginar que todas vez que carregar uma lista, eu determino um valor para que seja possível carregar, a pergunta é, qual combinações possível de valores posso carregar?

Esse tipo de inteligencia pode ser aplicado em vários casos comuns, como saber em tempo real quais combinações possível para um grupo de pessoas em quartos, saber qual a melhor combinação de itens para se colocar em um carrinho de compras ou ate mesmo quais conjuntos possíveis se colocar na mochila de uma viajem. O computador pode calcular tudo isso pra gente :D .

Vamos ao código:

function calcularSubConjuntosPossiveis(vetorLista,n,soma){

// Se o valor de subListaVetor[sum+1][n+1] for true então existe pelo menos um subconjunto possível

subListaVetor[soma+1][n+1];
var 1 = 0;
var j = 0;

// Se a soma de todos os itens for 0, resposta true

for(i = 0; i <= n; i++){
subListaVetor[0][i] =true;
}

// Se a soma dos itens não for 0, devemos verificar quais conjuntos possíveis existem

for(i = 1; i <= soma; i++){
subListaVetor[i][0] = false;
}

// Gera a matriz com combinações possíveis de conjuntos

for(i = 1; i <= soma; i++){

// colocar todos os valores no topo

for(j = 1; j <= n; j++){
subListaVetor[i][j] = subListaVetor[i][j-1];

//verifica se o item cabe dentro do conjunto e atualiza a posição dele dentro da matriz
if(i >= vetorLista[j-1]){
subListaVetor[i][j] = subListaVetor[i][j] || subListaVetor[i - vetorLista[j-1]][j-1];
}

}

}

// Vamos imprimir agora a nossa matriz, falado quais combinações de conjuntos possíveis

for (i = 0; i <= soma; i++){

for (j = 0; j <= n; j++){
document.write(subListaVetor[i][j]+” | “);
}

document.write(‘
‘);
}

// retorna true ou false, avisando se foi possível fazer a combinação de itens com os valores

return subListaVetor[soma][n];

}
Como resultado final, vamos ter uma matriz, falando true ou false, falando quais combinação possíveis por linha.