I am having problem with code I am writing which is supposed to take a list of boxes of varying size, and pack them into a single large container box.
The main method which is supposed to implement a solution is called fillContainerBox(). I have a basic nested if statement which will work for packing the first few boxes, but the code fails when it is necessary to unpack more than 1 box.
/**Container Box Class which sorts using recursion
*
* @author Richard McCormick
*/
public class ContainerBoxClass extends java.lang.Object
{
private static int CLEAR_BOX = 102;
private static int FILL_BOX = 101;
private static final char DEFAULT_FIELD_CHAR = 45;
private static final int MAX_NUM_BOXES = 26;
private static final int NO_BOXES_AVAILABLE = -1;
private BoxClass[] boxList = new BoxClass[MAX_NUM_BOXES];
private char[][] containerBoxField;
private int containerBoxHeight = 0;
private int containerBoxWidth = 0;
private int numBoxesAvailable = 0;
//Shows what you are doing
private boolean displayFlag = false;
/**Default constructor class
* @param initBoxHeight - Height of container
* @param initBoxWidth - Width of container
*/
ContainerBoxClass(int initBoxHeight, int initBoxWidth)
{
containerBoxHeight = initBoxHeight;
containerBoxWidth = initBoxWidth;
containerBoxField = new char[containerBoxWidth][containerBoxHeight];
//Populates field with empty values
for (int y = 0; y < containerBoxHeight; y++)
{
for (int x = 0; x < containerBoxWidth; x++)
{
containerBoxField[x][y] = DEFAULT_FIELD_CHAR;
}
}
displayFlag = false;
}
/**Adds a new box to list of boxes
* @param boxWidth
* @param boxHeight
* @return success
*/
public boolean addBoxToList(int boxWidth, int boxHeight)
{
//Initialize return
boolean success = false;
//Checks that there is room
if (numBoxesAvailable < MAX_NUM_BOXES)
{
//Creates a new box
BoxClass tempBox = new BoxClass(boxWidth, boxHeight);
tempBox.unsetUsedState();
//Increments available boxes
boxList[numBoxesAvailable] = tempBox;
numBoxesAvailable++;
//Success
success = true;
}
return success;
}
/**Checks location to see if box will fit
*
* @param testLocation - Point class
* @param testBox - Box class
*
* @return fits - Boolean indicator
*/
private boolean checkForFitInField(PointClass testLocation, BoxClass testBox)
{
boolean fits = false;
//Dimensions of testBox
int testWidth = testBox.getWidth();
int testHeight = testBox.getHeight();
//Position of test point
int testLocX = testLocation.getXPos();
int testLocY = testLocation.getYPos();
System.out.println("Test location: " + testLocX + " " + testLocY);
//Booleans to see if box is out of bounds or not
boolean inBoundsX = ((testLocX + testWidth) < containerBoxWidth);
boolean inBoundsY = ((testLocY + testHeight) < containerBoxHeight);
//If size fits within the container at desired location
if (inBoundsX && inBoundsY)
{
int numOccupied = 0;
//Iterates through location to determine if empty
for (int ycounter = testLocY; ycounter < (testLocY + testHeight); ycounter++)
{
for (int xcounter = testLocX; xcounter < (testLocX + testWidth); xcounter++)
{
//If there is something in location bounds, location not empty
if (containerBoxField[xcounter][ycounter] != DEFAULT_FIELD_CHAR)
{
numOccupied++;
}
}
}
if (numOccupied == 0)
{
fits = true;
}
}
return fits;
}
/**Displays the items in box
*
*/
public void displayField()
{
String row;
//Prints field from top down, to preserve order/location
for (int height = containerBoxHeight - 1; height >= 0; height--)
{
//Clears row each iteration
row = "";
//Iterates through columns in row
for (int width = 0; width < containerBoxWidth; width++)
{
//Checks to see if location is empty or not
if (containerBoxField[width][height] != DEFAULT_FIELD_CHAR)
{
row += " X ";
}
else
{
row += " " + DEFAULT_FIELD_CHAR + " ";
}
}
System.out.println(row);
}
System.out.println("===================================");
}
/**Fills a location in container box with a given box
*
* @param boxLocation - Location to pack box
* @param fillBox - Box to be packed
* @param clearFlag - Indicates if box is to be packed or removed
*/
public void fillBoxLocation(PointClass boxLocation, BoxClass fillBox, int clearFlag)
{
//Sets the starting and end positions for X-Axis
int xstart = boxLocation.getXPos();
int xend = xstart + fillBox.getWidth();
//Sets the starting and end positions for Y-Axis
int ystart = boxLocation.getYPos();
int yend = ystart + fillBox.getHeight();
//Output for testing
System.out.println("Attempting to fill box of size: " + fillBox.getWidth() + " " + fillBox.getHeight());
System.out.println("At location: " + xstart + " " + ystart);
//Iterates through each row
for (int ycounter = ystart; ycounter < yend; ycounter++)
{
//Iterates through each column
for (int xcounter = xstart; xcounter < xend; xcounter++)
{
//If clearFlag is set to fill box
if (clearFlag == FILL_BOX)
{
//Fill box
containerBoxField[xcounter][ycounter] = (char)FILL_BOX;
fillBox.setUsedState();
}
//Otherwise, erase box
else if (clearFlag == CLEAR_BOX)
{
containerBoxField[xcounter][ycounter] = (char)DEFAULT_FIELD_CHAR;
fillBox.unsetUsedState();
}
}
}
}
/**Attempts to fill the container class with boxes
*
* @return success - Boolean value indicating operation success
*/
public boolean fillContainerBox()
{
boolean success = false;
int currentBoxIndex = 0;
int previousBoxIndex = -1;
BoxClass currentBox;
BoxClass previousBox = new BoxClass();
PointClass currentLocation;
PointClass previousLocation = new PointClass();
while (findNextUnusedBoxIndex(0) != NO_BOXES_AVAILABLE)
{
currentBoxIndex = findNextUnusedBoxIndex(0);
currentBox = boxList[currentBoxIndex];
currentLocation = findNextOpenLocation();
BoxClass nextBox = boxList[currentBoxIndex + 1];
if (checkForFitInField(currentLocation, currentBox))
{
fillBoxLocation(currentLocation, currentBox, FILL_BOX);
PointClass nextLoc = new PointClass();
nextLoc = findNextOpenLocation();
if (checkForFitInField(nextLoc, nextBox) != true)
{
fillBoxLocation(currentLocation, currentBox, CLEAR_BOX);
fillBoxLocation(currentLocation, nextBox, FILL_BOX);
}
}
previousLocation = currentLocation;
previousBox = currentBox;
if (displayFlag)
{
displayField();
}
}
return success;
}
/**Finds the next open location in the container box
*
* @return openLocation - PointClass object containing first open location
*/
private PointClass findNextOpenLocation()
{
//Instantiates return variable as empty PointClass
PointClass openLocation = new PointClass();
//Boolean value which indicates whether location has been found
boolean hasLocation = false;
//Iterates through each row
for (int ycounter = 0; ycounter < containerBoxHeight; ycounter++)
{
//Iterates through each column
for (int xcounter = 0; xcounter < containerBoxWidth; xcounter++)
{
//If item at current location is empty, and no item has yet been found
if (containerBoxField[xcounter][ycounter] == DEFAULT_FIELD_CHAR && hasLocation == false)
{
//Set current location as first open location
openLocation.setXPos(xcounter);
openLocation.setYPos(ycounter);
//Indicate that location has been found
hasLocation = true;
}
}
}
//Return the open location
return openLocation;
}
/**Finds the next unused box in boxList, starting at provided index
*
* @param startAtIndex - Index to begin searching at
* @return indexFinal - Index of first unused box
*/
private int findNextUnusedBoxIndex(int startAtIndex)
{
//Sets up return and internal vars
int indexFinal = NO_BOXES_AVAILABLE;
int counter = startAtIndex;
//Iterates through available boxes
while (counter < numBoxesAvailable)
{
//If box has already been used, skip and increment
if (boxList[counter].isUsed())
{
counter++;
}
//Otherwise, return unused box index & terminate
else
{
indexFinal = counter;
counter = numBoxesAvailable;
}
}
//Return unused box index
return indexFinal;
}
/**Sets display flag
*
* @param setState - Boolean value to set displayFlag to
*/
public void setDisplayFlag(boolean setState)
{
//If display flag is not already equal to set state
if (setState != displayFlag)
{
//Set new flag state
displayFlag = setState;
}
}
}
Please excuse my messy code. I have been trying to find a solution but have not found one.
Consider using a greedy algorithm.
You start with a box (let's call it the package) that's going to contain the other boxes. Of the boxes you need to put into the package, put the largest box in first (You could acheive this by sorting your list of boxes by volume in descending order, E.G. [largest box, 2nd largest, ..., smallest box]) . Depending on the size of this box, the package might have some volume left over we can fill with other boxes. Now, in the remaining volumes we can try placing the second largest box following the same method used to fill the package. All we would have to do is partition the remaining space of the package and treat those partitions as smaller versions of the whole problem.