1

I have a rectangle size W x H and a bigger rectangle whose sides are of length that is a multiple of the GCD of W and H.

I am trying to determine the maximum amount of the smaller rectangles I can fit into the bigger rectangle. The smaller rectangles can be rotated. I also don't care about a slightly empty gap at the top right corner.

So far I have come up with:

// +-------------+ We have 3 potential sections to fill with rects. The
// |      C      | inital calculation is for section A. If A doesn't
// +-------+-----+ consume the entire area then we then try and fill the
// |       |     | other areas with the alternate rotation.
// |   A   |  B  |
// |       |     |
// +-------+-----+
//
int numWidthA = (int)Math.floor(width / rect[0]);
int numLengthA = (int)Math.floor(length / rect[1]);
int numWidthB = 0;
int numLengthB = 0;
int numWidthC = 0;
int numLengthC = 0;

double remainingWidth = width - (numWidthA * rect[0]);
double remainingLength = length - (numLengthA * rect[1]);

if(remainingWidth != 0) {
    double usedLength = numLengthA * rect[1];

    numWidthB = (int)Math.floor(remainingWidth / rect[1]);
    numLengthB = (int)Math.floor(usedLength / rect[0]);
}

if(remainingLength != 0) {
    numWidthC = (int)Math.floor(width / rect[1]);
    numLengthC = (int)Math.floor(remainingLength / rect[0]);
}

System.out.printf("Rotation: %.1f x %.1f%n", rect[0], rect[1]);
System.out.printf("A: %d x %d%n", numWidthA, numLengthA);
System.out.printf("B: %d x %d%n", numWidthB, numLengthB);
System.out.printf("C: %d x %d%n", numWidthC, numLengthC);

return (numWidthA * numLengthA) + (numWidthB * numLengthB) +
       (numWidthC * numLengthC);

This fails if the initial section, section A, is too greedy. It keeps consuming too much space such that there's not enough room for the alternate rotation in another section. I.e it leaves room for H/2 instead of H. If it uses all the room available, no problem, it's when it uses almost all the room.

I tried to recursively remove a rectangle until there was enough room for a multiple of the alternate rotation but I was having trouble due to double precision errors. So I was hoping there was an alternate solution?

I also didn't like that solution due to it taking the algorithm from O(1) to O(n)

Another problem is determining the initial rotation of the rectangle, at the moment I see which rotation consumes the most area and use that rotation for the section A.

4

0 回答 0