1
\$\begingroup\$

This is a follow up question to 3D bin packing in Java

public boolean put3D(final ItemsUnit[] item, final int p, final int n) {



/*
     * call intialization method to initialize the arrays
     */
    init(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[p]);   // 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[p]);   // 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[p]);   // 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
 * @param item
 * @param p
 * @return
 */
private boolean putL(final ItemsUnit[] item, final int p) {

    /*
     * remaining dimensions arrays already initialized in put3D
     */
    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[p].getLength())) {

            i = j;  //storing the item next to which we should put the new packed item
            minRemL = remainingLength[j];   //minimum length left

        } else {

            return false;
        }
    }

    remainingLength[p] = remainingLength[i] - item[p].getLength();   //update the remaining length of the new item added 
    remainingBreadth[p] -= item[p].getBreadth();    //update the remaining breadth of the new item added
    remainingHeight[p] -= item[p].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[p].getLength();   //increment x by the length of the new packed item in the extreme point of length

    System.out.println(" Place " + item[p].getUnit() + " of " + item[p].getiRef()+ " in the extreme point on the right ");

    return true;
}

/**
 * adding the new item to the extreme point in breadth
 * @param item
 * @param p
 * @return
 */
private boolean putB(final ItemsUnit[] item, final int p) {

    /*
     * remaining dimensions arrays already initialized in put3D
     */
    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[p].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[p].getBreadth();    //update the remaining breadth of the new item added 
    remainingHeight[p] -= item[p].getHeight();  //update the remaining height of the new item added
    remainingLength[p] -= item[p].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[p].getBreadth();  //increment y by the breadth of the new packed item in the extreme point of breadth

    System.out.println(" Place " + item[p].getUnit() + " of " + item[p].getiRef()+ " in the extreme point on the left of " + item[i].getUnit() + " of " + item[i].getiRef() );

    return true;
}


/**
 * adding the new item to the extreme point in height
 * @param item
 * @param p
 * @return
 */
private boolean putH(final ItemsUnit[] item, final int p) {

    /*
     * remaining dimensions arrays already initialized in put3D
     */
    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[p].getHeight() ) && ( item[i].getLength() >= item[p].getLength() )
                    && ( item[i].getBreadth() >= item[p].getBreadth() )  && ( item[i].isFragile() == false ) ) {

            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[p].getHeight();   //update the remaining height of the new item added 
    remainingBreadth[p] -= item[p].getBreadth();    //update the remaining breadth of the new item added
    remainingLength[p] -= item[p].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[p].getHeight();   //increment z by the height of the new packed item in the extreme point of height

    System.out.println(" Place " + item[p].getUnit() + " of " + item[p].getiRef()+ " in the extreme point above the " + item[i].getUnit() + " of " + item[i].getiRef() );

    return true;
}

This is the init() method to initialize the arrays:

/**
 * initialize the remaining dimensions' arrays
 * @param n
 */
public void init(final int n) {

    remainingLength = new double[n];
    remainingHeight = new double[n];
    remainingBreadth = new double[n];

    for (int i = 0; i < n; i++) {

        /*
         * initialize the remainingLength array to the length of the container
         */
        remainingLength[i] = length;

        /*
         * initialize the remainingHeight array to the height of the container
         */
        remainingHeight[i] = height;

        /*
         * initialize the remainingBreadth array to the breadth of the container
         */
        remainingBreadth[i] = breadth;
    }
}

These are the variables:

    private ArrayList<ItemsUnit> packedItems;
    private double x, y, z = 0;
    private double[] remainingLength;
    private double[] remainingHeight;
    private double[] remainingBreadth;

This is a part of a big project, so I cannot put all the classes and methods in my question.

I wrote the code without following any algorithm but I found out that it is close to the Extreme-Point-Based Heuristics and the Multi-Start Randomized Constructive Heuristic

Can someone go through my code and tell me if there is a problem in the algorithm I wrote?

\$\endgroup\$
  • \$\begingroup\$ Have you written any tests for this algorithm of yours? \$\endgroup\$ – ZeroOne Apr 18 '16 at 13:24
  • \$\begingroup\$ @ZeroOne First, I tested it with small sized items , for example having dimensions = (1,1,1) and a small container so that I can verify if it exceeds the container's dimensions or not. Then, I tested it with bigger sized items and a smaller container. Afterwards, I tested it with a really big container that can contain all items. For all the tests I did, the output was correct. But I need to verify the logic of my algorithm more. \$\endgroup\$ – Rii933 Apr 19 '16 at 9:02
  • \$\begingroup\$ Right, so what is it that you expect from this site? It sounds like you would like us to verify your algorithm for you. \$\endgroup\$ – ZeroOne Apr 19 '16 at 9:04
  • \$\begingroup\$ yes, is that possible? \$\endgroup\$ – Rii933 Apr 19 '16 at 9:08
  • 2
    \$\begingroup\$ If the code is reasonably tested, and works as far as the author knows, then it can be on-topic. We can review it for improvements. Reviewers are not obliged to "verify" the algorithm, strictly speaking. It's not uncommon that a bug comes to light only during review. \$\endgroup\$ – janos Apr 19 '16 at 10:46