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

我有一些不同大小的矩形框和一个更大的矩形框。我需要在更大的盒子里放入不同类别的盒子的最大数量。在任何情况下，每个类别的某些最小数量的框需要适应。基本上，我需要解决约束优化问题。我如何继续？将矩形框放在更大的矩形框中

2013-03-29 noddy

是否所有的箱子在同一类别的尺寸相同？ –

如果您决定使用蛮力递归方法，您可以尝试在每个可用位置放置下一个框，那么缩小解决方案空间而不丢失任何最佳解决方案的一种方法是限制新盒子的位置，以便它们必须始终请触摸左侧和底侧的现有盒子（或包含盒子的墙壁）。这是可行的，因为任何解决方案都可以转化为一个解决方案，即每个箱子通过向左和向下重复移动箱子直到不再有这种移动成为可能，从而遵守该限制。 –

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

不幸的是，这个问题没有多项式时间算法，即NP很难。

因此请尝试搜索。将箱子从大到小排序可能会有所帮助（按地区或一侧，不能说哪个更好，这取决于你如何搜索）。

如果速度远远不能接受，尝试部分贪婪以获得相当好的解决方案。

来源

2013-03-29 07:43:05 Topro

其实我正在寻找一个近似的解决方案，因为我知道NP-Hard中的问题。我似乎不能想办法解决问题 – noddy

哦......我不知道。如果这是一个现实世界的问题，我认为贪婪会很好。否则，你可能会看看A Star（A *），试着找一些好的评估函数 – Topro

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

回答

相关问题