Bin包裝與扭曲？

我一直在尋找某種算法來照顧我所遇到的問題。我遇到的最接近的事情是一個bin包裝算法，但我不認爲它的安靜，我正在尋找。Bin包裝與扭曲？

這份文件是我的問題的圖示和預期輸出： http://www.scribd.com/doc/90871434/Rectangles

我的想法在哪裏可以找到最低（高）的矩形，並創建滿足剩餘矩形的寬的長方形，並與一些遞歸找出其餘的。

我基本上試圖做的是找到最小數量的垂直堆疊的矩形，給定N個水平放置的矩形。

在Java中這樣做我有一個HashMap與輸入矩形。

任何想法，代碼，鏈接？謝謝

來源

2012-04-23 user1352234

我認爲你應該使用分而治之。

當你找到最低的矩形時，你也拆分你的數據集。下一個矩形不是排在左側就是右側。這是遞歸的。

來源

2012-04-24 00:22:28 bdecaf

找到最小的矩形。

創建你的第一個結果矩形。

確定剩餘的矩形。

將算法應用於所有連續的其餘矩形組。

來源

2012-04-23 20:54:06

啊是的，這是我的思路。問題是算法的一部分，就像遍歷HashMap的代碼一樣，最終將矩形放在正確的位置。 – user1352234 2012-04-23 21:08:14

更爲明顯的表示形式是從左到右排列的矩形數組。用這種表示法，實現上述算法就容易得多。最壞的情況是'O（n * n）'，它的平均值是'O（n log（n））'。如果該算法速度不夠快，我有一個更復雜的算法，即O（n log（n））最壞的情況。但複雜性可能不合理。 – btilly 2012-04-23 21:51:54

Bin包裝與扭曲？

回答

相關問題