这个问题真的很简单，我有一个随机大小的正方形数组（宽度，高度）和一个固定宽度的表面。在这个表面上排列正方形的最佳有效算法是什么？方格之间不能有无用的空隙。有可能吗？不使用人工智能或繁重的处理？
类似于这张图片的东西，但假设我的表面在底部没有界限，它是一个固定宽度和无界限高度的表面。
问问题
1503 次
3 回答
6
这个问题称为二维装箱。这是解决它的一种方法：
于 2012-07-27T08:03:59.573 回答
0
对于这样的事情，您可以使用Bin Packing Problem的变体，尝试在工作表中打包尽可能多的正方形，或者使用（可能看起来更合适的）Cutting Stock Algorithm。
但是请注意，在这两种情况下，您的方格之间不太可能没有间隙。
于 2012-07-27T08:07:51.353 回答
0
这种类型的优化问题被称为线性规划（linear optimization）。坏消息是它很复杂。
看看Simplex算法代数方法，还有比较通用的数值方法，搜索内点方法。
有免费的图书馆，如：LP_SOLVE
于 2012-07-27T08:17:28.090 回答