Solo por diversión, probé la solución de programación dinámica precisa. Escrito en Python, debido a mi confianza suprema de que no debe optimizar hasta que tenga que hacerlo ;-)
Esto podría proporcionarle un comienzo, o bien una idea aproximada de qué tan cerca puede llegar antes de recurrir a la aproximación.
Código basa en http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem, por lo tanto, el menos-que-informativos nombres de variables m, W, w, v.
#!/usr/bin/python
import sys
solcount = 0
class Solution(object):
def __init__(self, items):
object.__init__(self)
#self.items = items
self.value = sum(items)
global solcount
solcount += 1
def __str__(self):
#return str(self.items) + ' = ' + str(self.value)
return ' = ' + str(self.value)
m = {}
def compute(v, w):
coord = (len(v),w)
if coord in m:
return m[coord]
if len(v) == 0 or w == 0:
m[coord] = Solution([])
return m[coord]
newvalue = v[0]
newarray = v[1:]
notused = compute(newarray, w)
if newvalue > w:
m[coord] = notused
return notused
# used = Solution(compute(newarray, w - newvalue).items + [newvalue])
used = Solution([compute(newarray, w - newvalue).value] + [newvalue])
best = notused if notused.value >= used.value else used
m[coord] = best
return best
def main():
v = [int(l) for l in open('filesizes.txt')]
W = int(sys.argv[1])
print len(v), "items, limit is", W
print compute(v, W)
print solcount, "solutions computed"
if __name__ == '__main__':
main()
Por simplicidad sólo estoy teniendo en cuenta los tamaños de archivo: una vez que tenga la lista de tamaños que desee utilizar, se pueden encontrar algunos nombres de archivo con esos tamaños buscando a través de una lista, por lo que no tiene sentido que se enrede nombres de archivo en el núcleo, parte lenta del programa. También estoy expresando todo en múltiplos del tamaño del bloque.
Como puede ver, he comentado el código que proporciona la solución real (en lugar del valor de la solución). Eso fue para ahorrar memoria: la forma correcta de almacenar la lista de archivos utilizados no es una lista en cada Solución, sino que cada punto de solución debe volver a la Solución de la que se derivó. Luego, puede calcular la lista de tamaños de archivo al final volviendo a la cadena, generando la diferencia entre los valores en cada paso.
Con una lista de 100 tamaños de archivo generados aleatoriamente en el rango 2000-6000 (estoy asumiendo 2k bloques, por lo que son archivos de tamaño 4-12MB), esto resuelve para W = 40K en 100 segundos en mi computadora portátil . Al hacerlo, calcula 2,6 millones de posibles soluciones 4M.
La complejidad es O (W * n), donde n es el número de archivos. Esto no contradice el hecho de que el problema es NP completo. Así que, al menos, me estoy acercando a una solución, y esto es solo en Python no optimizado.
Claramente, ahora se requiere algo de optimización, porque en realidad necesita ser resuelto para W = 4M (8GB DVD) y cuantos archivos tenga (digamos unos miles). Suponiendo que el programa puede tomar 15 minutos (comparable al tiempo requerido para escribir un DVD), eso significa que actualmente el rendimiento es corto en un factor de aproximadamente 10^3. Tenemos un problema que es bastante difícil de resolver de forma rápida y precisa en una PC, pero no más allá de los límites de la tecnología.
El uso de la memoria es la principal preocupación, ya que una vez que comenzamos a pulsar el botón vamos a reducir la velocidad, y si nos quedamos sin espacio de direcciones virtual nos encontramos en un problema porque tenemos que implementar nuestro propio almacenamiento en el disco . Mi ejecución de prueba alcanza un máximo de 600 MB. Si escribió el código en C en una máquina de 32 bits, cada "solución" tiene un tamaño fijo de 8 bytes. Por lo tanto, podría generar una matriz masiva de 2-D sin realizar ninguna asignación de memoria en el bucle, pero en 2 GB de RAM solo podría manejar W = 4M y n = 67. Vaya, los DVD están fuera. Sin embargo, podría resolver casi por completo los CD de bloques de 2-k: W = 350k da n = 766.
Editar: La sugerencia de MAK para calcular iterativamente de abajo hacia arriba, en lugar de recursivamente de arriba hacia abajo, debe reducir enormemente los requisitos de memoria. Primero calcule m (1, w) para todos 0 < = w < = W. Desde esta matriz, puede calcular m (2, w) para todos 0 < = w < = W. Entonces puede tirar todos los m (1, w) valores: no los necesitará para calcular m (3, w) etc.
Por cierto, sospecho que en realidad el problema que desea resolver podría ser el bin packing problem, en lugar de solo la pregunta de cómo obtener lo más cerca posible de llenar un DVD. Eso es, si tiene muchos archivos, desea escribirlos todos en DVD, usando el menor número de DVD posible. Hay situaciones en las que es muy fácil resolver el problema del embalaje de la basura, pero resolver este problema es difícil. Por ejemplo, supongamos que tiene discos de 8GB y 15GB de archivos pequeños. Va a llevar un tiempo buscar para encontrar la coincidencia más cercana posible a 8GB, pero el problema del empaquetamiento de bandejas sería trivialmente resuelto simplemente colocando aproximadamente la mitad de los archivos en cada disco; no importa exactamente cómo los divide porque está va a perder 1GB de espacio haga lo que haga.
Dicho todo esto, hay heurísticas extremadamente rápidas que dan resultados decentes la mayor parte del tiempo. Lo más simple es ir a través de la lista de archivos (quizás en orden decreciente de tamaño), e incluir cada archivo si cabe, excluirlo de lo contrario. Solo necesita retroceder a algo lento si las soluciones aproximadas rápidas no son "lo suficientemente buenas", para su elección de "suficiente".
Me recuerda a http://xkcd.com/287/ – ruslik
Supongo que la definición correcta del problema sería "Cómo dividir estos archivos en el número mínimo de contenedores, para que los archivos de cada contenedor no excedan el límite de tamaño. ", y es un problema más difícil que la mochila. – ruslik