6.3.1. Problema de la mochila 0/1.
Idea: el resultado del problema de la mochila (no 0/1) es una cota superior válida para el problema de la mochila 0/1.
Demostración: Si una solución para el problema de la mochila 0/1 tiene valor vTOTAL, entonces esta es una solución válida para la mochila no 0/1. Por lo tanto, la solución óptima para el problema de la mochila no 0/1 será vTOTAL o mayor.
Estimacion (k, Q): Aplicar el algoritmo voraz para el problema de la mochila, con los elementos de k..n. Si los beneficios son enteros, nos podemos quedar con la parte entera del resultado anterior.
Ejemplo. n = 4; M = 7; v = (2, 3, 4, 5) w = (1, 2, 3, 4)