an algorithm design problem rectangle cover with different small rectangle or square

user_2791862 0
Viewed 242

This problem can be described as follows;

given a rectangle, the width and height can be randomly large number; and given some smaller rectangles or squares, means basic element, such as 6*6, 8*4, 4*4, 6*4, 4*4, 2*2, 1*1; is there some algorithm to cover the given rectangle efficiently? there are two constraints,

  1. it's better to use the same basic element;
  2. cover the bigger basic element first.

For example, give a 8*8 square; can be divided into one 6*6, and then seven 2*2; the other option is four 4*4; the other option is two 8*4; and another option is eight 1*1; and there are still some other options to get the 8*8 square. Use the two constraints given, will choose two 8*4 as best result.

Is there some good algorithm to solve this problem?

algorithm
1 Answers

Your Problem is a variant of the well known knapsack problem so may be do some research in this direction. It is NP-hard.

One thing that bothers me with your question is that your rating function is quite unspecified. So there is no value attached to your rectangles and no penalty for introducing another type of tile such that you can clearly say that for covering 10*10 area the solution 1 x 6*6, 1 x 4*6, 1 x 6*4, 1 x 4*4 (can the elements turned?) is better or worse than 25 x 2*2. Which constraint weights more: to have fewer different parts, or to have bigger components.

Based on this missing spec i would say the easiest approach is to use largest avaialbe tile those sides is an divider of the rectangle to fill. so that the solution is always n x i*j because this is a no-brain solution and always works and does not need any complex algorithm and its fits the first (the highest priority?!) constraint.

Little side notes:

Your problem appears also in lot of areas in industrial production for example within electrical engineering while designing circuit boards. Adding another different component also adds more costs than just the components price.
So it is desireable to keep the bill of materials (BOM) short and try to replace components that are used only once by other ones. E.g. on the circuit board. If there are a lot of 100Ohm resistors in the design already then it may be cheaper not to put a single 200Ohm resistor but put 2 100Ohm resistor there instead. So it can be avoid to have an additional item that you need to buy, you need to store, probably to test, and to set up in your production line....

user_23315920
Related