¿Cómo puedo saber rápidamente si existe una solución válida para empaquetar rectángulos más pequeños en un rectángulo más grande sin que se superpongan?

¿Puede siempre empaquetar rectángulos más pequeños en un solo rectángulo más grande único (conocido de antemano) sin superponerse si

  1. Cada pieza más pequeña cabe dentro del rectángulo más grande individualmente.
  2. El volumen total de todas las piezas más pequeñas es menor o igual que el rectángulo más grande.

No quiero el embalaje exacto, solo quiero saber si puedo asumir con seguridad que debe existir una solución si se cumplen las condiciones anteriores.

Contexto: necesito extender esto a tres dimensiones y necesito una heurística simple y rápida que me diga si teóricamente puede existir una posible solución o no.

¿Estás hablando de un rectángulo dentro de otro rectángulo o de varios rectángulos dentro de un único rectángulo más grande? Supongo que la superposición no está permitida, ¿verdad?
Lo siento, tienes razón, la superposición no está permitida y son varios rectángulos dentro de un único rectángulo más grande. Actualicé la pregunta.
La condición 2 no es suficiente. Considere un rectángulo grande de tamaño 11x5 (55 unidades) y 3 rectángulos pequeños de tamaño 6x3 (el área total es 54).
Tienes razón @ Ripi2. No creo que esto pueda resolverse de manera eficiente a través de una heurística.

Respuestas (1)

No, no puedes. Considere tratar de empacar un 2 × 2 y un 1 × 4 en un 2 × 5 rectángulo:

ingrese la descripción de la imagen aquí

Su área combinada es 8 < 10 , y cada uno cabe individualmente en el rectángulo, pero no pueden caber ambos al mismo tiempo.

En general, los problemas de empaque son difíciles de resolver; No veo ninguna razón para esperar un algoritmo eficiente para este problema de decisión, y probablemente debería confiar en la heurística o aceptar tiempos de ejecución más lentos para obtener respuestas exactas a través de enfoques de fuerza bruta.

¿Cómo puedo saber rápidamente si existe una solución válida para empaquetar rectángulos más pequeños en un rectángulo más grande sin que se superpongan?
RespuestasAquíPolítica de privacidad1y, 0v