Lleno, por favor. Script para llenar de manera óptima un CD o DVD

«¡Qué desperdicio!», pensamos cuando hemos acabado de grabar un CD o un DVD y no hemos podido aprovechar toda la capacidad de estos medios de almacenamiento.

Los usamos para guardar todo tipo de archivos: fotos, textos, copias de seguridad, películas… Yo lo uso, casi en exclusiva, para estas últimas —recodificadas, previamente, con recode ;-)—, así, en un DVD+R DL, puedo guardar entre diez y once películas.

Pensé en idear un algoritmo que me calculara cómo llenar de manera óptima un DVD, eligiendo de un grupo de archivos aquellos cuya suma de tamaños se acercara más a la capacidad del disco.

Pasó el tiempo y no era capaz de resolver el problema sin recurrir a la fuerza bruta. Este problema no es ni nuevo ni único. De forma genérica, se trata de llenar un contenedor de capacidad limitada con el máximo número de objetos de tamaño «x». Buscando por la red, encontré una solución muy buena de Thanassis Tsiodras que usa programación dinámica.

Continuar leyendo «Lleno, por favor. Script para llenar de manera óptima un CD o DVD»