Consideremos uma instância definida pelo primeiros i itens, 1 ≤ i ≤ n, com pesos w1, . . . , wi , valores v1, . . . , vi e mochila capacidade j, 1 ≤ j ≤ W. Seja F (i, j) o valor de uma solução ótima para este exemplo, ou seja, o valor do subconjunto mais valioso dos primeiros i itens que se enquadram em a mochila de capacidade j.
Podemos dividir todos os subconjuntos dos primeiros i itens que se ajustam a mochila de capacidade j em duas categorias: aquelas que não incluem o i-ésimo item e aqueles que o fazem.
1º) Entre os subconjuntos que não incluem o i-ésimo item, o valor de um ótimo subconjunto é, por definição, F (i − 1, j ).
2º) Entre os subconjuntos que incluem o i-ésimo item (portanto, j − wi ≥ 0), um ótimo subconjunto é composto por este item e um subconjunto ótimo dos primeiros i − 1 itens que cabe na mochila de capacidade j − wi . O valor de tal ideal subconjunto é vi + F (i − 1, j − wi ).
Assim, o valor de uma solução ótima entre todos os subconjuntos viáveis do primeiro i itens é o máximo desses dois valores. Claro, se o i-ésimo item não couber na mochila, o valor de um subconjunto ideal selecionado dos primeiros i itens é igual ao valor de um subconjunto ótimo selecionado dos primeiros i − 1 itens.
-
Nossa meta é encontrar o F(n, W), o valor máximo de um subconjunto dado n itens que cabem dentro de uma mochila de capacidade W, e seja um subconjunto ideal para ele.
-
Funções de memória
A abordagem direta de cima para baixo encontrar uma solução para tal recorrência leva a um algoritmo que resolve subproblemas mais de uma vez e, portanto, é muito ineficiente (normalmente, exponencial ou pior).
A abordagem clássica de programação dinâmica, por outro lado, funciona de baixo para cima: preenche uma tabela com soluções para todos os subproblemas menores, mas cada um deles eles são resolvidos apenas uma vez
- 1 more item...
Exemplo 02
Vamos aplicar o método da função de memória à instância considerada no Exemplo 1. Apenas 11 dos 20 valores não triviais (ou seja, não aqueles na linha 0 ou na coluna 0) foram calculados.
- 1 more item...