optimization - 不是背包或垃圾箱算法

Question

我需要找到一个矩形组合，以最大限度地利用圆的面积。我的情况和经典问题之间的区别在于我有一组我可以使用的矩形，以及我必须使用的这些矩形的一个子集。

打个比方：想想日志的结尾和电路板尺寸列表。我可以从原木上切割 2x4、2x6、2x8 和 2x10，但我必须至少切割两个 2x4 和一个 2x8。

据我了解，我的特定变体与其他打包优化略有不同。提前感谢您对我如何调整现有算法来解决此问题的任何见解。

NCD柴油机

Answer 1

这实际上是一个相当困难的问题，即使是正方形而不是矩形。

这是一个想法。将其作为一个背包整数程序来处理，它可以让您对解决方案有所了解。（根据定义，它不会为您提供最佳解决方案。）

IP 公式启发式

Say you have a total of n rectangles, r1, r2, r3, ..., rn
Let the area of each rectangle be a1, a2, a3, ..., an
Let the area of the large circle you are given be *A*

决策变量

Xi = 1 if rectangle i is selected. 0 otherwise.

客观的

 Minimize [A - Sum_over_i (ai * Xi)]

受制于：

 Sum_over_i (ai x Xi) <= A # Area_limit constraint
 Xk = 1 for each rectangle k that has to be selected

您可以使用任何求解器来解决此问题。

现在，这是一个启发式的原因是这个解决方案完全忽略了圆内矩形的排列。它还最终将矩形“切割”成更小的块以适合圆圈内。（这就是为什么 Area_limit 约束是一个弱界限。）

相关参考

这个数学 SE问题解决了它的“经典”版本。您可以查看其中作为评论提供的链接，了解几个巧妙的解决方案，包括将相同大小的正方形包装在一个圆圈内。