3D bin packing in Java

Question

I made some changes to the first code here I wrote and I want to know which one is more correct logically (before the changes or after the changes).

It's really hard to manually test these kind of problems.

This is the first code (without the changes):

public boolean put3D(ItemsUnit item, int p,int n) {
 //------if x still did not exceed the container's length
 if(x<length){
 //--------if we can put the new item next to the item packed in the extreme point of length
 if(putL(item,p)) {
 packedItems.add(item); // if item fits add it to the packedItems into the container
 return true;
 }
 }
 //------if y still did not exceed the container's breadth
 if(y<breadth) {
 //--------if we can put the new item next to the item packed in the extreme point of breadth
 if(putB(item,p)){
 packedItems.add(item); // if item fits add it to the packedItems into the container
 return true;
 }
 }
 //------if z still did not exceed the container's height
 if(z<height){ 
 //--------if we can put the new item next to the item packed in the extreme point of height
 if(putH(item,p)){
 packedItems.add(item); // if item fits add it to the packedItems into the container
 return true;
 }
 }
 return false; //return false if item cannot be packed in neither extreme point
 }
 //-----------adding the new item to the extreme point in length
 private boolean putL(ItemsUnit item, int p) {
 double minRemL=remainingLength[0]; //the minimum remaining length of all already packed items
 int i=0; //to store the index of the item next to which we should put the new item
 //--------choosing the point (position) where to put the new item----
 for (int j=0; j<remainingLength.length; j++){
 if ((remainingLength[j] != 0) && (minRemL >= remainingLength[j]) && (remainingLength[j] >= item.getLength())){
 i=j; //storing the item next to which we should put the new packed item
 minRemL=remainingLength[j]; //minimum length left
 }
 }
 remainingLength[p]=remainingLength[i]-item.getLength(); //update the remaining length of the new item added 
 remainingBreadth[p]-=item.getBreadth(); //update the remaining breadth of the new item added
 remainingHeight[p]-=item.getHeight(); //update the remaining height of the new item added
 remainingLength[i]=0; //insert 0 to the remainingLength of the item next to which we put the new item (so that we don't consider its remaining length anymore)
 x+=item.getLength(); //increment x by the length of the new packed item in the extreme point of length
 return true;
 }
 //-----------adding the new item to the extreme point in breadth
 private boolean putB(ItemsUnit item, int p) {
 double minRemB=remainingBreadth[0]; //the minimum remaining breadth of all already packed items
 int i=0;//to store the index of the item next to which we should put the new item
 //--------choosing the point (position) where to put the new item----
 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; //------return false if all the positions cannot fit the new item
 }*/
 }
 remainingBreadth[p]=remainingBreadth[i]-item.getBreadth(); //update the remaining breadth of the new item added 
 remainingHeight[p]-=item.getHeight();//update the remaining height of the new item added
 remainingLength[p]-=item.getLength(); //update the remaining length of the new item added
 remainingBreadth[i]=0; //insert 0 to the remainingBreadth of the item next to which we put the new item (so that we don't consider its remaining breadth anymore)
 y+=item.getBreadth(); //increment y by the breadth of the new packed item in the extreme point of breadth
 //x=length-remainingLength[p]; //update x to the position of the item next to which we put the new item
 return true;
 }
 //-----------adding the new item to the extreme point in height
 private boolean putH(ItemsUnit item, int p) {
 double minRemH=remainingHeight[0]; //the minimum remaining height of all already packed items
 int i=0; //to store the index of the item next to which we should put the new item
 //--------choosing the point (position) where to put the new item----
 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; //------return false if all the positions cannot fit the new item
 }*/
 }
 remainingHeight[p]=remainingHeight[i]-item.getHeight(); //update the remaining height of the new item added 
 remainingBreadth[p]-=item.getBreadth(); //update the remaining breadth of the new item added
 remainingLength[p]-=item.getLength();//update the remaining length of the new item added
 remainingHeight[i]=0; //insert 0 to the remainingHeight of the item next to which we put the new item (so that we don't consider its remaining height anymore)
 z+=item.getHeight(); //increment z by the height of the new packed item in the extreme point of height
 return true;
 }

I changed the code by adding:

 x=remainingLength[p]; // update x to the position of the new item added
 z=remainingHeight[p]; // update z to the position of the new item added
 y=remainingBreadth[p];// update y to the position of the new item added

This is the full code after changes:

public boolean put3D(ItemsUnit item, int p,int n) {
 //------if x still did not exceed the container's length
 if(x<length){
 z=remainingHeight[p]; // update z to the position of the new item added
 y=remainingBreadth[p];// update y to the position of the new item added
 //--------if we can put the new item next to the item packed in the extreme point of length
 if(putL(item,p)) {
 packedItems.add(item); // if item fits add it to the packedItems into the container
 return true;
 }
 }
 //------if y still did not exceed the container's breadth
 if(y<breadth) {
 x=remainingLength[p]; // update x to the position of the new item added
 z=remainingHeight[p]; // update z to the position of the new item added
 //--------if we can put the new item next to the item packed in the extreme point of breadth
 if(putB(item,p)){
 packedItems.add(item); // if item fits add it to the packedItems into the container
 return true;
 }
 }
 //------if z still did not exceed the container's height
 if(z<height){ 
 x=remainingLength[p]; // update x to the position of the new item added
 y=remainingBreadth[p];// update y to the position of the new item added
 //--------if we can put the new item next to the item packed in the extreme point of height
 if(putH(item,p)){
 packedItems.add(item); // if item fits add it to the packedItems into the container
 return true;
 }
 }
 return false; //return false if item cannot be packed in neither extreme point
 }
 //-----------adding the new item to the extreme point in length
 private boolean putL(ItemsUnit item, int p) {
 double minRemL=remainingLength[0]; //the minimum remaining length of all already packed items
 int i=0; //to store the index of the item next to which we should put the new item
 //--------choosing the point (position) where to put the new item----
 for (int j=0; j<remainingLength.length; j++){
 if ((remainingLength[j] != 0) && (minRemL >= remainingLength[j]) && (remainingLength[j] >= item.getLength())){
 i=j; //storing the item next to which we should put the new packed item
 minRemL=remainingLength[j]; //minimum length left
 }
 }
 remainingLength[p]=remainingLength[i]-item.getLength(); //update the remaining length of the new item added 
 remainingBreadth[p]-=item.getBreadth(); //update the remaining breadth of the new item added
 remainingHeight[p]-=item.getHeight(); //update the remaining height of the new item added
 remainingLength[i]=0; //insert 0 to the remainingLength of the item next to which we put the new item (so that we don't consider its remaining length anymore)
 x+=item.getLength(); //increment x by the length of the new packed item in the extreme point of length
 return true;
 }
 //-----------adding the new item to the extreme point in breadth
 private boolean putB(ItemsUnit item, int p) {
 double minRemB=remainingBreadth[0]; //the minimum remaining breadth of all already packed items
 int i=0;//to store the index of the item next to which we should put the new item
 //--------choosing the point (position) where to put the new item----
 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; //------return false if all the positions cannot fit the new item
 }*/
 }
 remainingBreadth[p]=remainingBreadth[i]-item.getBreadth(); //update the remaining breadth of the new item added 
 remainingHeight[p]-=item.getHeight();//update the remaining height of the new item added
 remainingLength[p]-=item.getLength(); //update the remaining length of the new item added
 remainingBreadth[i]=0; //insert 0 to the remainingBreadth of the item next to which we put the new item (so that we don't consider its remaining breadth anymore)
 y+=item.getBreadth(); //increment y by the breadth of the new packed item in the extreme point of breadth
 //x=length-remainingLength[p]; //update x to the position of the item next to which we put the new item
 return true;
 }
 //-----------adding the new item to the extreme point in height
 private boolean putH(ItemsUnit item, int p) {
 double minRemH=remainingHeight[0]; //the minimum remaining height of all already packed items
 int i=0; //to store the index of the item next to which we should put the new item
 //--------choosing the point (position) where to put the new item----
 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; //------return false if all the positions cannot fit the new item
 }*/
 }
 remainingHeight[p]=remainingHeight[i]-item.getHeight(); //update the remaining height of the new item added 
 remainingBreadth[p]-=item.getBreadth(); //update the remaining breadth of the new item added
 remainingLength[p]-=item.getLength();//update the remaining length of the new item added
 remainingHeight[i]=0; //insert 0 to the remainingHeight of the item next to which we put the new item (so that we don't consider its remaining height anymore)
 z+=item.getHeight(); //increment z by the height of the new packed item in the extreme point of height
 return true;
 }

I need to know which one is logically correct.

• dabadaba: You should really clean up you style, mainly the comments and throw some spaces in!!
• Rii933: @dabadaba yeah , I am still testing the code so cleaning it up is not really my priority. I just need to know if it's correct and efficient before styling it.

Answer 1

In this case, what you ought to do is write tests that attempt to pack various items into a box. Perhaps you could iterate over a set of boxes each 1 to 3 large in each of the 3 dimensions, (makes for 27 different boxes), that you then try to put into a larger box. Maybe try putting 4 (531441 combinations) (or maybe 5, but that's gonna take a while, 14348907 different combinations) of those boxes into a 4x4x4 cube, and the algorithm that packs the most wins? (if you're gonna pack 5 boxes, try 5x5x5 cube or 4x5x5 cube).

Maybe start small with 1-2 in all dimensions, 3 cubes in a 3x3x3 cube. (2*2*2 means 8 different boxes, 3 of those boxes means 8*8*8 possible box combinations [that's 512], meaning that even if your code takes a full second to test both algorithms like that, it'll be done in 10 minutes. Compare that to the other case which could take weeks at 1 second per combination and a day at 0.1 seconds per combination, which is too long for you to make sense out of.)

For performance of such a test, you could skip cases where the volume of the boxes to put in the cube is greater than the volume of the cube, as the algorithm should fail to put in all the boxes.

You'd need to record any differences in results between the two algorithms and print out those cases and see which algorithm is better like that. Then you can inspect the differences to see if there's any weird behaviour.

Like that, you can objectively test the correctness of each algorithm. Be sure to check if each item is actually in the box and doesn't clip with other items, or you'll find that the buggiest algorithm wins.

• Rii933: Thank you so much!! I tested the two algorithms like you said and now I know which one is not correct. The second code showed more efficient solutions than the first one. I will accept your answer!
• Pimgd: @Rii933 once you clean up the code like you put in the comment, post a follow up and we can talk about the code itself =)
• Rii933: ok, I will do that!