我在矩形容器中将具有不同大小和数量的矩形对象进行最佳放置时出现问题。使用二维装箱算法之一可以很好地解决问题，但只能用于空容器。对我来说，它几乎总是不是一个案例。我的容器可以有一个限制的地方，不能放置任何物体。 Packing example带容器中预定义间隙的2D容器包装
当然我不是谁遇到这样的问题，第一个，我希望有人已经开发了它一个很好的解决方案。任何事情都很好：书籍参考资料，文章，代码片段等。 形式化算法首选神经网络和这种类型的东西。
解决它的一种可能的方法是整数线性规划。有不同的模型，但这是一个简单的模型（有一点问题，但如果需要，您可以改进）。
分割问题变成一个主问题和子问题，与主问题看起来像这样：
minimize sum(p)
s.t.
for all i: sum[j] p[j]*count[j,i] >= n[i]
p[i] >= 0 (and integer, don't add this constraint)
其中：
p是决策变量，决定如何许多情况下使用将可用物品“包装”到容器中。显然有太多的事先列出，但它们可以动态生成。count[j,i]是包装j包含项目i的次数。n[i]是我们想要项目i的次数。>=，因为包装一些额外的项目是可以的，它可以让我们使用更少的不同包装（否则主要问题将需要特殊的“故意次优”包装才能实现约束）。开始每个项目一对夫妇哑填料，这样肯定是有一些解决，糟糕，因为它可能是。你甚至可以在容器中放置一个项目，即使没有使用子问题的求解器也是如此，但是子问题必须要解决，因此你可以在这里重新使用它。
子问题是找出可以改进当前解决方案的主要问题。因此，采取主控问题C的行的双重成本（也有因为有不同类型的项目为多），解决
maximize y.C
s.t.
1) for all i: y[i] <= n[i]
2) for all i: y[i] = sum[j] P[j] if j is a placement of item i
3) for all cells (a,b): sum[j] P[j] (if j covers a,b) <= 1
4) for all existing packings e: e.y <= sum(e) - 1
y >= 0 and integer
P boolean
其中，
y是隐含的，从跟随变量P,y[i]的选择是在包装中出现物品i的次数。P是真正的决策变量，决定是否使用特定项目的特定位置。示例问题中有62个不同的项目布局，包括旋转。如果主要问题是常规线性程序，但是它是一个整数程序，并且在分支约束4需要明确阻止重新创建之后，不会发生重新创建列。例如，在“低”分支上（回想这意味着我们采用了一些变量k，其分数值为f并将其限制为<= ⌊f⌋），子问题试图做的第一件事是重新创建完全相同的包装对应于k，因此可以将其添加到主问题中以“撤销损坏”。这与我们需要的完全相反。所以重新创建一个列必须被禁止。
约束条件4不是一个很好的方法，因为现在子问题将尝试生成所有的填充，这要归功于对称性。例如，下舍入本包装的可变后：
它产生相当于填料喜欢这些：
等有很多的这些和它们都毫无意义，因为它没关系（对于主问题的客观值，当考虑整数约束时）其中 1x3片段，它只是很重要的包装包含1x3件和14 1x1件。
所以理想的约束4将被更复杂的东西，禁止包装相当于到任何一个已经来过了，但别的东西，主要的工作原理是首先尝试高科取代。至少在这个例子中，这很好。
在此示例中，在添加允许主问题最佳（但在任何分支之前仍为分数）的列后，目标值为5.5882352941176467。这已经意味着我们知道我们至少需要6个容器，因为这是最佳的分数值，证明它不能用5来完成，而容器的分数不是一个选项。
与6个Container的解决方案很快发现，即
其中三个：
每个下列操作之一：
哪个包所有的作品加上一个额外的1×4片和3额外1x1件。
该算法不依赖于件或容器的形状，除非它们必须可以表示为网格上的单元格。该容器可以在整个地方都有孔，这些碎片可以更像是俄罗斯方块，甚至可以有分离的部分。不利的一面是，它所需的展示位置列表与容器的大小严重不符。
根据基本算法，它可能只需要很小的调整就可以将其从“普通矩形”更改为“带孔洞的矩形”。你想用什么？ – harold
其实我还没有选择一个原因，我不知道哪一个可以以最好的方式适应我的目的。对我来说，似乎任务可以通过修改最大矩形算法来完成，但我不确定。 – Dmytro