4.3.1. Problema de la mochila.
Ejemplos: n = 4; M = 10
w = (10, 3, 3, 4)
v = (10, 9, 9, 9)
Criterio 1: S = (1, 0, 0, 0). Valor total = 10
Criterio 2 y 3: S = (0, 1, 1, 1). Valor total = 27
w = (10, 3, 3, 4)
v = (10, 1, 1, 1)
Criterio 1 y 3: S = (1, 0, 0, 0). Valor total = 10
Criterio 2: S = (0, 1, 1, 1). Valor total = 3
Los criterios 1 y 2 pueden dar soluciones no muy buenas.
El criterio 3 garantiza siempre una solución óptima.
Demostración (por reducción al absurdo): Supongamos que tenemos una solución óptima, que incluye un objeto i, pero no incluye (o incluye con menor proporción x) otro objeto j con mejor proporción: (xi > xj) y (vi/wi < vj/wj).
Si quitamos un trozo de peso de i y lo metemos de j entonces obtendríamos más beneficio. Por ejemplo, si quitamos un peso p, con 0 < p ? xi·wi , p ? (1-xj)·wj:
vNUEVO = vANTIGUO - p*vi/wi + p*vj/wj = vANTIGUO + p*(vj/wj - vi/wi) > vANTIGUO