將矩形框放在更大的矩形框中

我有一些不同大小的矩形框和一個更大的矩形框。我需要在更大的盒子裏放入不同類別的盒子的最大數量。在任何情況下，每個類別的某些最小數量的框需要適應。基本上，我需要解決約束優化問題。我如何繼續？將矩形框放在更大的矩形框中

2013-03-29 noddy

是否所有的箱子在同一類別的尺寸相同？ –

如果您決定使用蠻力遞歸方法，您可以嘗試在每個可用位置放置下一個框，那麼縮小解決方案空間而不丟失任何最佳解決方案的一種方法是限制新盒子的位置，以便它們必須始終請觸摸左側和底側的現有盒子（或包含盒子的牆壁）。這是可行的，因爲任何解決方案都可以轉化爲一個解決方案，即每個箱子通過向左和向下重複移動箱子直到不再有這種移動成爲可能，從而遵守該限制。 –

矩形框是2D還是3D？ –

不幸的是，這個問題沒有多項式時間算法，即NP很難。

因此請嘗試搜索。將箱子從大到小排序可能會有所幫助（按地區或一側，不能說哪個更好，這取決於你如何搜索）。

如果速度遠遠不能接受，嘗試部分貪婪以獲得相當好的解決方案。

來源

2013-03-29 07:43:05 Topro

其實我正在尋找一個近似的解決方案，因爲我知道NP-Hard中的問題。我似乎不能想辦法解決問題 – noddy

哦......我不知道。如果這是一個現實世界的問題，我認爲貪婪會很好。否則，你可能會看看A Star（A *），試着找一些好的評估函數 – Topro

將矩形框放在更大的矩形框中

回答

相關問題