6.3.1. Problema de la mochila 0/1.
Si la solución óptima es de la forma s = (1, 1, 1, X, X, 0, 0, 0) entonces se alcanza antes la solución generando primero 1 (y luego 0).
Si es de la forma s = (0, 0, 0, X, X, 1, 1, 1) será mejor empezar por 0.
Idea: es de esperar que la solución de la mochila 0/1 sea “parecida” a la de la mochila no 0/1. Si ordenamos los objetos por vi/wi entonces tendremos una solución del primer tipo.
Utilizar una representación de la solución como un conjunto de los elementos incluidos. S = (s1, s2, ..., sm) donde m?n y si ? {1, 2, ..., n}.