5.3.2. Problema de la mochila 0/1.
Igual que en el tema anterior, pero los objetos no se pueden fragmentar en trozos más pequeños.
Problema: Tenemos n objetos, cada uno con un peso (wi) y un beneficio (vi), y una mochila en la que podemos meter objetos, con una capacidad de peso máximo M. El objetivo es maximizar el beneficio de los objetos transportados, donde cada objeto se puede coger entero (xi=1) o nada (xi=0).
Definición de la ecuación recurrente:
Sea Mochila (i, m) el problema de la mochila, considerando sólo los i primeros objetos (de los n originales) con una capacidad de peso m. Supondremos que devuelve el valor de beneficio total: ? xa·va
Podemos definir el problema de forma recurrente, en función de que se use o no el objeto i.