Vamos considerar uma instância definida pelos primeiros i itens, 1 ≤ i ≤ n, com pesos w1, ... ,wi, valores v1, ... ,vi e capacidade da mochila j, 1 ≤ j ≤ W. Seja F(i, j) o valor do subconjunto mais valioso dos primeiros i itens que cabem na mochila de capacidade j. Podemos dividir todos os subconjuntos dos primeiros i itens que cabem na mochila de capacidade j em duas categorias: aqueles que não incluem o i-ésimo item e aqueles que incluem.
Observe o seguinte:
- Entre os subconjuntos que não incluem o i-ésimo item, o valor de um subconjunto ótimo é, por definição, F(i - 1, j).
- Entre os subconjuntos que incluem o i-ésimo item, um subconjunto ótimo é composto por este item e um subconjunto ótimo vi + F(i - 1, j - wi) dos primeiros i - 1 itens que cabem na mochila de capacidade j - wi.