## 2.3.4 EL PROBLEMA DE LA MOCHILA FRACCIONARIA

Un ladrón encuentra n artículos en una tienda:

- El i-ésimo artículo cuesta vi pesos y pesa wi kilos

- Quiere tomar lo más valioso que pueda en una carga

- Puede cargar a lo más W kilos en su mochila para algún W.

- Puede tomar fracciones de artículos siempre y cuando no se exceda el peso límite W.

¿Qué cantidad y de qué artículos debe tomar el ladrón para maximizar el valor del botín?

Algoritmo ávido

- Tomar tanto del artículo con el valor más alto por kilo ( vi / wi) como se pueda.
- Si se acaba un artículo, tomar del siguiente artículo con valor ( vi / wi) más alto.
- Continuar hasta que se llene la mochila.

Si tenemos una solución óptima al problema de la mochila O = { o1, o1, …, oj} con j elementos.

Supongamos que existe una solución voraz G = { g1, g1, …, gk} con k elementos ordenados de acuerdo a la elección voraz.

Queremos mostrar que existe una solución óptima O’ que incluye la elección voraz g1.

- CASO 1: g1 no es fraccional.
  - Si g1 esta en O, no hay nada que probar.
  - Si g1 no esta en O, arbitrariamente quitamos w g1 en artículos de O y lo reemplazamos con g1 par a producir O’.
  - O’ es una solución y es tan buena como O.

- CASO 2: g1 es fraccional ( K = f* wg1 donde f es la fracción de g1 elegida y K es el límite de peso).
  - Si O incluye f* w g1 unidades de g1, n o hay nada que probar.
  - Si O incluye menos de f de g1, quitamos f* w g1 peso de O arbitrariamente y lo reemplazamos con f* w g1 unidades de g1 par a construir O’.
  - O’ es una solución válida y al menos tan buena como O.

Se demostró que hay una solución óptima O’ que contiene a g1 y Después de elegir g1 el límite de peso es K’’ = K – w g1 y el conjunto de artículos se convierte en I’’ = I – { g1} y Sea P’’ el problema de la mochila con límite de peso K’’ y lista de artículos I’’. Debemos probar que O’’ = O’–{ g1} es una solución óptima de P’’.

Probamos por contradicción:

- Asumimos que O’’ no es una solución de P’’. Sea Q una solución óptima con más valor que O’’.
- Sea R = Q ∪ { g1}. El valor de O’ es igual al valor de O’’ + g1.
- El valor de R es mayor que el valor de O’ = O’’ + g1.
- Como O’ era una solución óptima, esta es una contradicción.

Dado un conjunto de n actividades a realizar

- S = {1, 2, …, n }
- Todas las actividades requieren el mismo recurso (p.e. el mismo salón de clases) y lo utilizan uno a la vez.
- Cada actividad i tiene un tiempo de inicio si y de fin fi, si≤ fi, [ si, fi )
- Dos actividades i y j son com patibles si no se traslapan: si ≥ fi ó sj≥ fj
- Problema: Elegir el conjunto más grande de actividades compatibles.
  - Asumir que la entrada esta ordenada por f1 ≤ f2 ≤ … ≤ fn ( O ( nlg n)).

###