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, por exemplo:
Average Rating