Calculo de superficies
Buenas...
No se si esta es la categoría adecuada, ya que más bien parece un problema matemático, pero bueno, hay va.
Tengo que cortar piezas de un tablón aprovechando al máximo el mismo.
Por ejemplo:
Un tablón de 8*4
- Cortar piezas de:
- 2*2 una
- 1*2 una
- 1*1 tres
- 0.5*1 dos
¿Cuál sería la forma correcta para desperdiciar el mínimo del tablón?
¿Alguien tiene una idea?
Gracias.
No se si esta es la categoría adecuada, ya que más bien parece un problema matemático, pero bueno, hay va.
Tengo que cortar piezas de un tablón aprovechando al máximo el mismo.
Por ejemplo:
Un tablón de 8*4
- Cortar piezas de:
- 2*2 una
- 1*2 una
- 1*1 tres
- 0.5*1 dos
¿Cuál sería la forma correcta para desperdiciar el mínimo del tablón?
¿Alguien tiene una idea?
Gracias.
1 Respuesta
Respuesta de abarquin
1
Efectivamente es un problema de matemáticas, es un problema de Máximos y Mínimos, lo que es lo mismo, de derivadas.
Explícate un poco mejor que es lo que quieres hacer con el tablón porque no me entero.
- Tenemos: Un tablón de 8x4
- Queremos:
- Sacar el máximo número de astillas...
- Cortarlos de manera que al hacerme un casco me quepa la cabeza.
- Hacer un cubo con la máxima capacidad (puedes ponértelo de casco)...
- Quiero sacar 4 piezas para hacerme un Lego Technics...
:)
Explícate un poco mejor que es lo que quieres hacer con el tablón porque no me entero.
- Tenemos: Un tablón de 8x4
- Queremos:
- Sacar el máximo número de astillas...
- Cortarlos de manera que al hacerme un casco me quepa la cabeza.
- Hacer un cubo con la máxima capacidad (puedes ponértelo de casco)...
- Quiero sacar 4 piezas para hacerme un Lego Technics...
:)
- Tenemos un tablón de x*y.
De dicho tablón queremos cortar z piezas de distintos tamaños desperdiciando el mínimo del mismo, colocando las piezas del "puzzle" en la posición óptima.
Por ejemplo:
Tablón de 8*4 mts
Cortar piezas de:
- Una pieza de 2*2 mts
- una de 1*2 mts
- Cuatro de 1*0.5 mts
El tablón sobrante debe ser de 6*4
¿Mejor?
Gracias.
De dicho tablón queremos cortar z piezas de distintos tamaños desperdiciando el mínimo del mismo, colocando las piezas del "puzzle" en la posición óptima.
Por ejemplo:
Tablón de 8*4 mts
Cortar piezas de:
- Una pieza de 2*2 mts
- una de 1*2 mts
- Cuatro de 1*0.5 mts
El tablón sobrante debe ser de 6*4
¿Mejor?
Gracias.
De nuevo xabi,
El caso es que hay demasiadas variables para poder considerar directamente una ecuación, por lo cual deberás utilizar un algoritmo:
1.- Comprobar que el tamaño de las fichas no excede del del tablón lo primero.
2.- Luego conseguir sumar el máximo número de lados posibles de sub-tablones para que encaje exactamente con el del tablón original, o al menos que se aproxime mucho.
3.- Y luego ir "permutando" las combinaciones de los tablones.
Las posibilidades de optimización no deben hacer referencia a que la superficie aprovechada sea máxima (que siempre será la misma), sino a que la altura dentro del tablón sea la mínima (Es igual que el algoritmo de inteligencia que resolvería el puzzle del famoso TETRIS).
El caso es que hay demasiadas variables para poder considerar directamente una ecuación, por lo cual deberás utilizar un algoritmo:
1.- Comprobar que el tamaño de las fichas no excede del del tablón lo primero.
2.- Luego conseguir sumar el máximo número de lados posibles de sub-tablones para que encaje exactamente con el del tablón original, o al menos que se aproxime mucho.
3.- Y luego ir "permutando" las combinaciones de los tablones.
Las posibilidades de optimización no deben hacer referencia a que la superficie aprovechada sea máxima (que siempre será la misma), sino a que la altura dentro del tablón sea la mínima (Es igual que el algoritmo de inteligencia que resolvería el puzzle del famoso TETRIS).
Pues eso.
De nuevo xabi,
Como referencia decirte que el algoritmo que necesitas lo vendía El Corte Inglés dentro de un programa de patronaje textil por la friolera de 14 kilos.
Pero bueno, no es tan complicado hacerlo, ahora bien, ¿en qué lenguaje lo vas a hacer? Tu verás.
El pseudocódigo sería como:
1.- Crear un tipo Tabla que recogiera las dimensiones de una tabla (x, y).
2.- Crearíamos dentro del programa tantos objetos tabla como tuviéramos más uno para el tablón principal.
3.- Primero comprobaríamos que se pueden sacar tantas tablas: Área = BasexAltura de manera que la superficie del tablón no excediera la de las tablillas.
4.- Comprobar que ninguna tabla es más larga que el tablón, por lo que ninguno de los lados de las tablas debe ser mayor que alguno de los del tablón.
5.- Una vez hecho esto, nos ponemos a ordenarlos.
6.- Creamos una matriz booleana de puntos en memoria, si la unidad son centímeros, pues centímetros, del tamaño del tablón. La vaciamos entera: Todo=0 o False, como quieras.
7.- Insertamos un tablón abajo a la izquierda en una de las posturas (horizontal o vertical). Cambiamos los valores de la matriz para que lo contenga (poner unos).
8.- Colocamos otro tablón. Intentando:
Que el lateral de todos los tabloncillos sea máximo respecto al tablón principal, vamos que se desperdicie lo menos posible. Y siempre intentamos colocar los tablones de manera que lleguen lo menos alto posible (lo que te dije del tetris).
9.- Tienes que llevar una variable con la ALTURA por la que vas del tablón y otra variable lista con el orden de los tablones.
10.- Terminas el algoritmo escogiendo de todas las posturas que has intentado aquella en que la ALTURA conseguida sea menor.
Mucha tela.
Alvaro.
Como referencia decirte que el algoritmo que necesitas lo vendía El Corte Inglés dentro de un programa de patronaje textil por la friolera de 14 kilos.
Pero bueno, no es tan complicado hacerlo, ahora bien, ¿en qué lenguaje lo vas a hacer? Tu verás.
El pseudocódigo sería como:
1.- Crear un tipo Tabla que recogiera las dimensiones de una tabla (x, y).
2.- Crearíamos dentro del programa tantos objetos tabla como tuviéramos más uno para el tablón principal.
3.- Primero comprobaríamos que se pueden sacar tantas tablas: Área = BasexAltura de manera que la superficie del tablón no excediera la de las tablillas.
4.- Comprobar que ninguna tabla es más larga que el tablón, por lo que ninguno de los lados de las tablas debe ser mayor que alguno de los del tablón.
5.- Una vez hecho esto, nos ponemos a ordenarlos.
6.- Creamos una matriz booleana de puntos en memoria, si la unidad son centímeros, pues centímetros, del tamaño del tablón. La vaciamos entera: Todo=0 o False, como quieras.
7.- Insertamos un tablón abajo a la izquierda en una de las posturas (horizontal o vertical). Cambiamos los valores de la matriz para que lo contenga (poner unos).
8.- Colocamos otro tablón. Intentando:
Que el lateral de todos los tabloncillos sea máximo respecto al tablón principal, vamos que se desperdicie lo menos posible. Y siempre intentamos colocar los tablones de manera que lleguen lo menos alto posible (lo que te dije del tetris).
9.- Tienes que llevar una variable con la ALTURA por la que vas del tablón y otra variable lista con el orden de los tablones.
10.- Terminas el algoritmo escogiendo de todas las posturas que has intentado aquella en que la ALTURA conseguida sea menor.
Mucha tela.
Alvaro.
