2
$\begingroup$

I am looking for an algorithm that can return the maximum number of rectangles in the same size with given width and height that fit in to a rectangle with given height and width.

For an example let's say I have a small rectangle with height of 50mm and width of 70mm and a bigger rectangle with height of 1200mm and width of 1000mm. I want to arrange the small rectangles inside the bigger rectangle in a fully utilize way. The small rectangles can be arrange in anyway (Small rectangle can rotated as well), I just want the number of small rectangles that I can put in the bigger rectangle in a maximum utilize way.

Thank you for your help!

$\endgroup$
2
  • $\begingroup$ I want to get the maximum possible number of rectangles. With "maximum utilize way" I just want to say I want to minimize the not allocated area of the bigger rectangle. Hope you get it. Thank you very much. $\endgroup$ Commented Oct 29, 2020 at 17:45
  • $\begingroup$ @KavinduGunawardena, so overall, you are trying to make an algorithm to calculate the maximum number of rectangles of given parameters you can tile the larger rectangle with, right ? $\endgroup$
    – Spectre
    Commented Oct 29, 2020 at 17:58

2 Answers 2

3
$\begingroup$

In your example, you can form a rectangle of 1,000 x 1,050 leaving 1,000 x 150, then a rectangle of size 150 x 980, leaving 150 x 20, which is less than a small rectangle, and therefore cannot be improved.

In general, this will be hard and involve systematically trying out various combinations.

$\endgroup$
1
  • $\begingroup$ Yeah it's quite hard and involve various combinations as well. If you can go to [this] (onpallet.com) site you can have an idea what I actually need sir. Thank you very much for your support sir. $\endgroup$ Commented Oct 31, 2020 at 5:13
1
$\begingroup$

If you want to take only positive integer sides into consideration, you can take a value that yields the highest possible quotient with a non-zero remainder. The best thing to do here (I am not that sure, but let it be so :D)is to take the remainder as $1$ , subtract it from the longer side of the larger rectangle and find the remaining number's smallest proper divisor. If the side minus one yields a length that has a prime number as its magnitude, subtract another $1$ from the value you have at hand and do the above steps. But please take care not to end up in a place where the next dividend you take can be divided by the remainder at hand - that's where you can put a decision point whether to abort that iteration or not.

Another thing is that the smaller side must either be divisible or leave a small remainder when divided by the remainder.

I am not sure if this helps, but I felt this would work. Please do notify me if I did the wrong thing.

$\endgroup$
3
  • $\begingroup$ Sure sir let me try in this way. Thank you very much for your support $\endgroup$ Commented Oct 31, 2020 at 5:13
  • $\begingroup$ @KavinduGunawardena , please don't call me sir.. I am just 15 yrs old ! 😂 $\endgroup$
    – Spectre
    Commented Oct 31, 2020 at 6:27
  • $\begingroup$ @KavinduGunawardena , a tip : if this algorithm goes faulty, try tweaking parts of it to correct it. Good luck ! $\endgroup$
    – Spectre
    Commented Oct 31, 2020 at 6:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .