algorithm for finding least area occupied with n rectangulars
I have a number of rectangular, I want to find the smallest rectangular which can cover all small ones. no rotation is allowed.
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?
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.
链接地址: http://www.djcxy.com/p/63242.html上一篇: 找到满足一定约束的矩阵
下一篇: 算法寻找最小面积占用n个矩形