0

I have a number of rectangular, I want to find the smallest rectangular which can cover all small ones. no rotation is allowed. enter image description here

Using brute force I want to find my answer. I am trying to code it in java. I know I should check all permutation of my n items and find the least area. And in order to make it easier first I tried to find min possible area. Then I used a 2 dimensional array with Boolean values to check if each cell is occupied or not. But I could not figure it out (code it).

How to check if my items can be placed in my limited area? For example I located my first item in x[0][0] to x[10][1] and make all cell in this range true, but I don't know how to tell my program to check other cell for next item. Can you tell me about steps which my algorithm need to implement?

Rishit Sanmukhani
  • 2,159
  • 16
  • 26
S S abbasi
  • 29
  • 1
  • 6

1 Answers1

0

Your problems falls under the category of 2D-bin packing. It is an NP-hard problem, so there doesn't exist an efficient polynomial time algorithm for solving it. (Unless P==NP).

You could either try Brute force algorithm or clever heuristics which will give you fairly optimal solution.

Refer the following links:
1. How is 2D bin packing achieved programmatically? (For discussing various algorithms)
2. http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu (For implementation details)
3. http://www.binpacking.4fan.cz/ (for visualizing different heuristics)

Your brute force algorithm is very inefficient. The permutation in which the rectangles can be placed are very huge and difficult to find. I suggest you try above mentioned algorithms, which are easier to implement than finding going to all permutations.

Community
  • 1
  • 1
Rishit Sanmukhani
  • 2,159
  • 16
  • 26