.
“Durante un robo, el ladrón encuentra un botín más cuantioso de lo esperado y tiene que elegir qué llevarse. Su saco puede transportar como máximo W kilos. En el botín hay n objetos que pesan w1,…, wn kilos y valen v1,…, vn euros. ¿Qué objetos debe elegir para llevarse el máximo valor sin que se rompa el saco?”
Este podría ser un enunciado habitual del conocido problema de la mochila. Este problema surge con mucha frecuencia en el ámbito de la informática: simplemente sustituye “peso” por “tiempo de CPU” y “mochila de capacidad máxima W” por “hay disponibles W unidades de tiempo de CPU”; o de manera similar “tiempo de CPU” por “ancho de banda”. Este problema es NP-completo y, al igual que para el problema de la suma de subconjuntos mencionado en una entrada anterior, puede encontrarse un algoritmo pseudo-polinómico para resolverlo. Más concretamente, vamos a diseñar un algoritmo que resuelve el problema en tiempo O(nW).
Uno de los puntos clave para diseñar un algoritmo de programación dinámica consiste en encontrar los subproblemas en que puede descomponerse el problema original. En este caso, podríamos optar por dos posibilidades: a) considerar mochilas de menos capacidad que W; b) considerar menos objetos que n. Tomemos la primera opción y definamos la función K(w) como:
K(w) = máximo valor obtenible con una capacidad de w.
Veamos cómo puede expresarse esta función en términos de algunos subproblemas. Si la solución óptima de K(w) incluye el objeto i, entonces la eliminación del objeto i nos proporcionará la solución óptima de K(w-wi). Dicho de otra manera, K(w) simplemente es K(w-wi)+vi para algún i. Como no sabemos para qué i, tenemos que probar todas las posibilidades, es decir:
Y con esto ya casi lo tenemos, sólo falta escribir las cinco líneas del algoritmo:
K[0]=0;
para w=1 hasta W hacer
K[w]=max{K[w-wi]+vi | wi<=w }
fpara;
devuelve K[W]
Este sencillo algoritmo rellena un vector de longitud W+1. Como rellenar cada posición puede costar O(n) unidades de tiempo, el tiempo total de ejecución es O(nW).
En la página http://people.csail.mit.edu/bdean/6.046/dp/ podéis encontrar interesantes clases de programación dinámica impartidas en el MIT (Massachusetts Institute of Technology). Entre los problemas tratados se encuentra el problema de la mochila (Integer Knapsack Problem).
Fuente: S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms, McGraw-Hill, 2008.