Algoritmo de embalaje del contenedor 3D usando Java? -- java campo con performance campo con algorithm campo con combinatorics camp codereview Relacionados El problema

3D bin packing algorithm using Java?


3
vote

problema

Español

Escribí un algoritmo de embalaje de contenedor 3D, pero todavía no estoy seguro de si es correcto o no.

No seguí ningún código o pseudo-código, es por eso que me gustaría saber si es un algoritmo eficiente para el problema de embalaje del contenedor 3D o no.

Cada contenedor tiene una longitud, altura y amplitud

Cada artículo tiene una longitud, altura y amplitud.

Este es el código que escribí para empacar los elementos uno por uno sin exceder la longitud, la altura o la amplitud del contenedor:

  private double x,y,z=0; private double[] remainingLength; private double[] remainingHeight; private double[] remainingBreadth;     //----initialize the remaining dimensions' arrays     public void init(int n) {         remainingLength=new double[n];         remainingHeight=new double[n];         remainingBreadth=new double[n];         for (int i=0; i<n; i++) {             remainingLength[i]=length;             remainingHeight[i]=height;             remainingBreadth[i]=breadth;         }     }  public boolean put3D(ItemsUnit item, int p,int n) {     init(n);       if(x<length){         if(putL(item,p)) {         packedItems.add(item); // if item fits add it to the packedItems into the container      return true;     }     }          if(y<breadth) {                 if(putB(item,p)){             packedItems.add(item); // if item fits add it to the packedItems into the container             return true;         }         }             if(z<height){                 if(putH(item,p)){                 packedItems.add(item); // if item fits add it to the packedItems into the container                 return true;             }         }          return false;     }  public boolean putL(ItemsUnit item, int p) {     //remaining dimensions arrays already initialized in the optimization algorithm     double minRemL=remainingLength[0];     int i=0;      for (int j=0; j<remainingLength.length; j++){         if ((remainingLength[j]!=0)&&(minRemL>=remainingLength[j])&&(remainingLength[j]>=item.getLength())){                 i=j; //choosing the item to which we should put the new packed item next to                 minRemL=remainingLength[j]; //minimum length left         }else {             return false;         }     }         remainingLength[p]=remainingLength[i]-item.getLength();         remainingBreadth[p]-=item.getBreadth();         remainingHeight[p]-=item.getHeight();         remainingLength[i]=0;         x+=item.getLength(); //increment x         return true; }   public boolean putB(ItemsUnit item, int p) {     //remaining dimensions arrays already initialized in the optimization algorithm     double minRemB=remainingBreadth[0];     int i=0;      for (int j=0; j<remainingBreadth.length; j++){         if ((remainingBreadth[j]!=0)&&(minRemB>=remainingBreadth[j])&&(remainingBreadth[j]>=item.getBreadth())){                 i=j; //choosing the item to which we should put the new packed item next to                 minRemB=remainingBreadth[j]; //minimum length left         }         else {             return false;         }     }         remainingBreadth[p]=remainingBreadth[i]-item.getBreadth();         remainingHeight[p]-=item.getHeight();         remainingLength[p]-=item.getLength();         remainingBreadth[i]=0;         y+=item.getBreadth(); //increment y         return true; }   public boolean putH(ItemsUnit item, int p) {     //remaining dimensions arrays already initialized in the optimization algorithm     double minRemH=remainingHeight[0];     int i=0;      for (int j=0; j<remainingHeight.length; j++){         if ((remainingHeight[j]!=0)&&(minRemH>=remainingHeight[j])&&(remainingHeight[j]>=item.getHeight())){                 i=j; //choosing the item to which we should put the new packed item next to                 minRemH=remainingHeight[j]; //minimum length left         }         else {             return false;         }     }         remainingHeight[p]=remainingHeight[i]-item.getHeight();         remainingBreadth[p]-=item.getBreadth();         remainingLength[p]-=item.getLength();         remainingHeight[i]=0;         z+=item.getHeight(); //increment z         return true; }   

He probado el algoritmo y funcionó bien sin exceder las dimensiones del contenedor, pero no estoy completamente seguro de que el código es correcto.

¿Puede alguien leer el código y decirme si tiene un problema en algún lugar o si es correcto?

Original en ingles

I wrote a 3D bin packing algorithm but I am still not sure if it is correct or not.

I did not follow any code or pseudo-code that's why I would like to know if it is an efficient algorithm for the 3D bin packing problem or not.

each container has a length, height and breadth

each item has a length , height and breadth.

This is the code I wrote to pack items one by one without exceeding the container's length, height or breadth:

private double x,y,z=0; private double[] remainingLength; private double[] remainingHeight; private double[] remainingBreadth;     //----initialize the remaining dimensions' arrays     public void init(int n) {         remainingLength=new double[n];         remainingHeight=new double[n];         remainingBreadth=new double[n];         for (int i=0; i<n; i++) {             remainingLength[i]=length;             remainingHeight[i]=height;             remainingBreadth[i]=breadth;         }     }  public boolean put3D(ItemsUnit item, int p,int n) {     init(n);       if(x<length){         if(putL(item,p)) {         packedItems.add(item); // if item fits add it to the packedItems into the container      return true;     }     }          if(y<breadth) {                 if(putB(item,p)){             packedItems.add(item); // if item fits add it to the packedItems into the container             return true;         }         }             if(z<height){                 if(putH(item,p)){                 packedItems.add(item); // if item fits add it to the packedItems into the container                 return true;             }         }          return false;     }  public boolean putL(ItemsUnit item, int p) {     //remaining dimensions arrays already initialized in the optimization algorithm     double minRemL=remainingLength[0];     int i=0;      for (int j=0; j<remainingLength.length; j++){         if ((remainingLength[j]!=0)&&(minRemL>=remainingLength[j])&&(remainingLength[j]>=item.getLength())){                 i=j; //choosing the item to which we should put the new packed item next to                 minRemL=remainingLength[j]; //minimum length left         }else {             return false;         }     }         remainingLength[p]=remainingLength[i]-item.getLength();         remainingBreadth[p]-=item.getBreadth();         remainingHeight[p]-=item.getHeight();         remainingLength[i]=0;         x+=item.getLength(); //increment x         return true; }   public boolean putB(ItemsUnit item, int p) {     //remaining dimensions arrays already initialized in the optimization algorithm     double minRemB=remainingBreadth[0];     int i=0;      for (int j=0; j<remainingBreadth.length; j++){         if ((remainingBreadth[j]!=0)&&(minRemB>=remainingBreadth[j])&&(remainingBreadth[j]>=item.getBreadth())){                 i=j; //choosing the item to which we should put the new packed item next to                 minRemB=remainingBreadth[j]; //minimum length left         }         else {             return false;         }     }         remainingBreadth[p]=remainingBreadth[i]-item.getBreadth();         remainingHeight[p]-=item.getHeight();         remainingLength[p]-=item.getLength();         remainingBreadth[i]=0;         y+=item.getBreadth(); //increment y         return true; }   public boolean putH(ItemsUnit item, int p) {     //remaining dimensions arrays already initialized in the optimization algorithm     double minRemH=remainingHeight[0];     int i=0;      for (int j=0; j<remainingHeight.length; j++){         if ((remainingHeight[j]!=0)&&(minRemH>=remainingHeight[j])&&(remainingHeight[j]>=item.getHeight())){                 i=j; //choosing the item to which we should put the new packed item next to                 minRemH=remainingHeight[j]; //minimum length left         }         else {             return false;         }     }         remainingHeight[p]=remainingHeight[i]-item.getHeight();         remainingBreadth[p]-=item.getBreadth();         remainingLength[p]-=item.getLength();         remainingHeight[i]=0;         z+=item.getHeight(); //increment z         return true; } 

I tested the algorithm and it worked fine without exceeding the dimensions of the container but I am not fully certain if the code is correct.

Can anyone read the code and tell me if it has a problem somewhere or if it is correct?

           

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

Cada uno de los putL , putB1 y putH es público sin necesidad de ser. Una llamada a cualquiera de estos métodos puede lanzar una excepción si el método 99887766555443333 no se ha llamado antes porque la matriz no ha sido inicializada. La llamada a init debe hacerse en el constructor para evitar dichos efectos secundarios.


Tener espacios antes y después (condicional), los operadores aumentarán la legibilidad. E.g este

  if ((remainingHeight[j]!=0)&&(minRemH>=remainingHeight[j])&&(remainingHeight[j]>=item.getHeight())){     

sería mejor como este

  if ((remainingHeight[j] != 0) && (minRemH >= remainingHeight[j]) && (remainingHeight[j] >= item.getHeight())){     
 

Each of the putL, putB and putH methods is public without needing to be. A call to any of these methods can throw an exception if the put3D method hasn't been called before because the array haven't been initialised. The call to init should be done in the constructor to avoid such side effects.


Having spaces before and after (conditional) operators will increase the readability. E.g this

if ((remainingHeight[j]!=0)&&(minRemH>=remainingHeight[j])&&(remainingHeight[j]>=item.getHeight())){   

would be better like this

if ((remainingHeight[j] != 0) && (minRemH >= remainingHeight[j]) && (remainingHeight[j] >= item.getHeight())){   
 
 
1
 
vote

No soy codificador, pero puedo ver una falla inmediata. Para mantener el código simple, ha comparado las dimensiones (L / B / H) del paquete con las dimensiones respectivas restantes de la caja (L / B / H).

Si bien este es un buen comienzo, definitivamente no es óptimo. El caso en el que el paquete se puede girar para encajar en el espacio restante no se ha aceptado aquí.

 

I am no coder but can see an immediate flaw. In order to keep the code simple, you have compared dimensions (l/b/h) of package with the remaining respective dimensions of the box (l/b/h).

While this is a good start, it is definitely not optimal. The case where the package can be rotated to fit into the remaining space has not been taken into accord here.

 
 

Relacionados problema

3  Encuentra todas las combinaciones distintas de letras en una cadena  ( Find all distinct combinations of letters in a string ) 
Me he estado preparando para las entrevistas y recogiendo moderno C ++. Una pregunta reciente que hice fue encontrar todas las combinaciones (o subconjuntos d...

4  Permodificar codility  ( Permcheck codility ) 
El siguiente código obtiene un 100% en el Permdeck tarea en la CODILIDAD . Debe ser O (n). La pregunta es: Se da una matriz no vacía que consta de n ent...

15  Cracker de contraseña de fuerza bruta  ( Brute force password cracker ) 
Escribí este script para una prueba de concepto JavaScript Password Cracker: var charset = " !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_...

7  Generar un diccionario de contraseñas  ( Generate a dictionary of passwords ) 
Tengo un script de Python que genera un diccionario de todas las combinaciones de contraseña posibles de 3 dígitos. Esencialmente funciona solo en la anidació...

1  Reto de primos consecutivos en Codeeeval.com  ( Consecutive primes challenge at codeeval com ) 
Estoy trabajando a través de un nuevo desafío en Codeeeval.com y creo que estoy obteniendo un resultado correcto, pero no puedo pasar por su alumnador. No est...

1  Imprima todos los tamaños posibles de subsecuencias de cadena en C  ( Print out all possible sizes of subsequences of string in c ) 
Por ejemplo, dada una cadena "abcdefghijk", quiero que mi función se imprima: a, b, c, d, e, f, g, h, i, j, k. ab, bc, cd, de, ef, fg, gh, hi, ij, jk ab...

1  Encuentra la frecuencia de combinaciones en un gran conjunto de datos  ( Find frequency of combinations in large data set ) 
Mi preocupación es el rendimiento del Código. Se tarda mucho más de lo que me gustaría. Estaría dispuesto a renunciar a un poco de memoria para un mayor rendi...

10  Función recursiva que genera las permutaciones de una cadena  ( Recursive function that generates the permutations of a string ) 
Estoy buscando una revisión de mi función recursiva que genere las permutaciones de una cadena. ¿Hay mejores formas de hacer esto? var permutations = []; ...

1  Encuentra triángulos de la línea  ( Find triangles from line ) 
Tengo algunas líneas que forman triángulos. Me gustaría desafiar la forma más rápida de encontrar todos los triángulos. En particular, el código debe tom...

3  Mi implementación de permutación lexicográfica en F # es 3x más lenta que C #  ( My implementation of lexicographic permutation in f is 3x slower than c ) 
¿Puede alguien ayudarme con la siguiente micro optimización para el código F # para la permutación lexicográfica? Tengo código en C # que se ejecuta para 0,...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos