- Llenándose
- Leída
- Respuesta
Problema de la mochila
Solo puedes cargar cierto peso, y cada objeto tiene un peso y un valor. ¿Qué objetos te llevas para cargar el mayor valor? Probar todas las combinaciones duplica el trabajo con cada objeto. Una tabla con una fila por objeto y una columna por capacidad encuentra la mejor mochila celda a celda. Toca un objeto para meterlo en la mochila y vuelve a tocarlo (en la mochila o en el estante) para sacarlo. La mochila se llena según el peso, y los recuadros muestran los dólares que has metido frente al máximo posible. Pulsa Carga óptima para ver la mejor mochila. En el panel puedes cambiar los kilos y los dólares de los objetos, añadir o quitar objetos y fijar la capacidad de la mochila. La vista Tabla muestra cómo la programación dinámica encuentra la mejor mochila: pulsa Reproducir para ver cómo se llena la tabla, o Paso y Atrás para avanzar de paso en paso, y arrastra el control de pasos para saltar a cualquier punto. Cada fila añade un objeto, cada columna es una capacidad en kilos y cada celda contiene el máximo de dólares que cabe. Con la tabla seleccionada, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Toca las cajas para meterlas en la mochila y mira cómo se llena según el peso en kilos.
- Intenta llegar al mejor valor posible en dólares, o pulsa Carga óptima para ver la mejor mochila.
- Abre la vista Tabla y pulsa Reproducir para ver cómo cada celda elige entre meter y dejar un objeto.
Cómo funciona la tabla
Cada fila añade un objeto y cada columna es una capacidad, desde 0 hasta la de la mochila. Una celda guarda el mayor valor que cabe en esa capacidad usando los objetos hasta su fila. Sin el objeto nuevo, es la celda de arriba. Con él, si cabe, es el valor del objeto más el mejor valor para el peso que queda, que está en la fila de arriba, tantas columnas a la izquierda como pesa el objeto. La celda se queda con el mayor de los dos. La primera fila, sin objetos, es toda ceros.
Reconstruir los objetos
La celda de abajo a la derecha es el mejor valor. Para encontrar los objetos, empieza ahí y compárala con la celda de arriba: si es igual, el último objeto no hacía falta; si es mayor, el objeto está en la mochila, así que resta su peso y ve a esa columna. Sube una fila cada vez hasta llegar a la primera. La app muestra esta reconstrucción en naranja y enumera los objetos metidos debajo de la tabla.
Preguntas frecuentes
¿Qué significa 0/1 en el problema de la mochila 0/1?
Cada objeto se mete una vez o ninguna, nunca en parte y nunca dos veces. Si los objetos se pudieran partir, como granos de arroz, meter primero el mejor valor por peso sería óptimo; ese es el problema de la mochila fraccionaria.
¿Por qué no meter primero el mejor valor por peso?
Porque los objetos enteros pueden dejar huecos. Con una capacidad de 7 y objetos de peso 1, 3, 4 y 5 que valen 1, 4, 5 y 7, el mejor valor por peso es el del objeto de peso 5, que solo deja sitio para el objeto de peso 1, con un total de 8. Los objetos de peso 3 y 4 juntos valen 9.
¿Es rápido el algoritmo de la mochila?
La tabla tiene (número de objetos + 1) por (capacidad + 1) celdas, y cada una se llena en un paso. Es rápido para capacidades pequeñas, pero una capacidad puede ser un número enorme, así que en general el problema es NP-difícil; el método de la tabla se llama pseudopolinómico.
¿Se puede meter el mismo objeto dos veces?
Aquí no. En el problema de la mochila no acotada, cada objeto se puede tomar cualquier número de veces; la tabla lee entonces la celda de la izquierda en la misma fila en lugar de la fila de arriba, como en la app del cambio de monedas.
¿Se envía algo a algún sitio?
No. Todo se calcula en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor