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\$

closed as unclear what you're asking by Peter Taylor, dfhwze, VisualMelon, IEatBagels, Heslacher Aug 22 at 16:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\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