Current location - Quotes Website - Personality signature - An algorithm problem (preferably in java)
An algorithm problem (preferably in java)
Take a look, it seems not easy!

You can combine each rectangular object with only two length attributes, namely length and width.

The less space between them, the better, that is, the closer to their area, the better!

However, the key point lies in this combination process. The closer the lengths are, the more their edges will overlap, but it seems difficult. If the attribute graph has a corresponding algorithm, look back when you are free!

_______________________________________________________________

You should also add an attribute to rectangle: direction, that is, let it be placed horizontally or vertically. As for oblique placement, you don't have to consider it!

Algorithm:

1) can find rectangles with equilateral conditions. First, splice these rectangles into a rectangle.

Then find out that one of the rectangles is equal to the sum of several rectangular sides, and splice these rectangles together (but this may not be optimal). Finally, find those splicing with close sides and you will know that there is no new rectangle! But the mathematical foundation is not enough, and there is no way to formally prove the minimum value.

2) In addition, the exhaustive method (which is applicable when n is not large) can be used, which can be completely realized, that is, the combined arrangement (including the complete arrangement of relative positions and directions (two rotation directions)). For example, when N=2, there are four effective combinations of their relative positions. Calculate every possibility and choose the smallest one as OK!

However, the efficiency of this algorithm is relatively low. Of course, many of them are repetitive, and the algorithm can be optimized!

Summary: All the above are written while thinking, which is very casual. But the second algorithm is certainly feasible, but it needs to be optimized. I don't have enough knowledge of mathematics, so I can only go here. As for implementation, it is easy, as long as the algorithm is good. Let's stop here for the sake of time! ~ But your topic is quite interesting! If someone has a good algorithm, as expected. ...