我编写的代码有问题，该代码应该采用不同大小的盒子列表，并将它们打包到一个大容器盒子中。
实现解决方案的主要方法称为fillContainerBox()。我有一个基本的嵌套if语句，它将用于打包前几个盒子，但当需要打开多个盒子时，代码会失败。
/**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;
}
}
}
请原谅我的代码太乱了。我一直在努力寻找解决方案，但没有找到。
考虑使用贪婪算法。
你从一个盒子开始(我们称之为包(，它将包含其他盒子。在你需要放入包装的盒子中，先放入最大的盒子(你可以通过按体积降序排列盒子列表来实现这一点，例如[最大的盒子，第二大的盒子，…，最小的盒子](。根据这个盒子的大小，包裹可能还有一些剩余的体积，我们可以用其他盒子填充。现在，在剩下的卷中，我们可以尝试按照填充包的相同方法放置第二大盒子。我们所要做的就是对包的剩余空间进行分区，并将这些分区视为整个问题的较小版本。