5.3.2. Problema de la mochila 0/1.
Definición de la ecuación recurrente:
Si no se usa el objeto i: Mochila (i, m) = Mochila (i - 1, m)
Si se usa: Mochila (i, m) = vi + Mochila (i - 1, m - wi)
Mochila (i, m) = max (Mochila (i-1, m), vi + Mochila (i-1, m - wi))
Si (iɘ) ó (mɘ) entonces no hay solución: Mochila (i, m) = -?
En otro caso, si (i=0) ó (m=0) la solución es no incluir ningún objeto: Mochila (i, m) = 0
Definición de las tablas:
La solución del problema original será Mochila (n, M).
Por lo tanto necesitamos una tabla: V: array [0..n, 0..M] of integer.
V[i, j] = Beneficio máximo usando los i primeros objetos y peso j.