我想写，生成用于条块面板绘制的应用程序。

我有N个隔间（二维矩形）（N < = 40）。对于每个隔间，都有一个最小高度（minHeight [i]）和最小宽度（minWidth [i]）关联。面板本身也有一个MAXIMUM_HEIGHT约束。

这些N个柜子必须按照列方式排列，以便每个柜子满足上述限制条件。

此外，每列的宽度由该列中每个隔间的最大宽度决定。

此外，每列的高度应该是相同的。这决定了面板的高度

我们可以在任何列中留下的空白处添加备用隔间，或者我们可以将任何隔间的高度/宽度增加到指定的最小值以外。但是我们不能旋转任何隔间。

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

目前我已经通过忽略优化中的隔间宽度来实现它。我只是选择最大的minHeight隔间，并尝试将其安装在我的面板中。但是，它不保证最佳解决方案。

我能比这更好吗？

EDIT 1：问题目的：面板=2100毫米，minwidth范围（350毫米至800mm），范围了minHeight（225毫米到2100毫米）

编辑2的MAXIMUM_HEIGHT TO MINIMIZE面板的宽度（未面板区域）。

来源

2013-08-30 Abhishek Bansal

我试图围绕问题的高度部分包围我的想法。你堆积隔间？您是否必须在顶部的隔间上提供楼梯或梯子？ –

是的，柜子一个叠在另一个上面，做一个'柱子'。可以有一个或多个并排放置的这种列。每列应具有相同的高度（即<= MAXIMUM_HEIGHT）。 MAXIMUM_HEIGHT是2100mm，因此不需要楼梯或梯子。对不起，我不明白你的查询的这一部分。 –

这是一个2D问题，不涉及3D元素。 –

制剂

鉴于：

针对每个小区i = 1, ..., M中，（分钟）宽度W_i和（分钟）高度H_i
任何堆栈的最大允许高度，T

我们可以制定混合integer program如下：

minimize sum { CW_k | k = 1, ..., N } 
with respect to 

    C_i in { 1, ..., N },      i = 1, ..., M 

    CW_k >= 0,         k = 1, ..., N 

and subject to 

[1] sum { H_i | C_i = k } <= T,     k = 1, ..., N 

[2] CW_k = max { W_i | C_i = k },    k = 1, ..., N 
      (or 0 when set is empty)

可以拾取N是任何足够大的整数（例如，N = M）。

算法

插件该混合整数规划到一个现有的混合整数规划解算器，以确定由最佳C_i, i = 1, ..., M值给出的细胞至列映射。

这是你不想改造自己的部分。使用现有的求解器！

注

根据您的混合整数规划求解程序包的表达能力，你可能会或可能无法直接适用我上述类似。如果约束[1]和[2]不能使用，因为它们或max的性质，可以手动转换配方的相当于，声明较少，但更规范的一个，并不需要这种表现力的“基于数据集”的规定：

minimize sum { CW_k | k = 1, ..., N } 
with respect to 

    C_i_k in { 0, 1 },       i = 1, ..., M; k = 1, ..., N 

    CW_k >= 0,         k = 1, ..., N 

and subject to 

[1] sum { H_i * C_i_k | i = 1, ..., M } <= T, k = 1, ..., N 

[2] CW_k >= W_i * C_i_k,       i = 1, ..., M; k = 1, ..., N 

[3] sum { C_i_k | k = 1, ..., N } = 1,   i = 1, ..., M

这里从（在{ 1, ..., N }取的值）之前的C_i变量已被替换C_i_k变量的关系C_i = sum { C_i_k | k = 1, ..., N }下（在{ 0, 1 }服用值）。

最终的单元格到列映射由C_i_k描述：单元格i属于列k当且仅当C_i_k = 1。

来源

2013-09-03 17:05:38

不应该最后一行是'max'而不是'min'？ –

@Heuster是的，错字。 :) –

谢谢你的回答！其实我只能从符号中理解一点点。 N是列数？它如何确保每个单元格只出现在1列中？对不起，你能否详细说明你的问题表述？再次感谢！ –

一种解决方案是将隔间行宽度除以最小宽度。这可以为您提供可连接的最大数量的隔间。

将第一个除法的其余部分除以隔间的数量。这给你额外的宽度，以增加到最小宽度，使所有的机柜宽度均匀。

示例：您有一个63米的隔间排。每个房间的最小宽度为2米。我假设其中一个隔间墙的厚度包含在2米内。我还假设一个最后一个隔间会贴墙。

做数学，我们得到63/2 = 31.5或31个房间。

现在我们将0.5米乘以31个隔间并获得16毫米。所以，柜子宽度是2.016米。

来源

2013-08-30 17:23:50

列不一定都是相同的宽度。即需要将狭窄的隔间放在狭窄的柱子和宽的隔间中。 –

此外，每个隔间的最小宽度和高度也不相同。（对不起非常复杂的场景）:) –

@AbhishekBansal：好的，我的错误。您可以使用与我的答案相同的想法，除非您按照排序的最小宽度顺序将隔间放在行中，降序排列。您仍然将剩余空间均匀分配给该行中的所有隔间。 –

您可以查看vm打包特别是虚拟机搭配的共享感知算法：http://dl.acm.org/citation.cfm?id=1989554。你也可以阅读关于@http://en.m.wikipedia.org/wiki/Bin_packing_problem。问题已经很难了，但隔间可以分享宽度或高度。因此搜索空间变大了。

来源

2013-09-03 08:00:52 Bytemain

感谢您的链接。这似乎很有趣，但我无法适应这个问题以适应我的需要。有任何想法吗？ –

在vm中打包项目共享空间。总尺寸可以小于每个单独的项目。 http://en.m.wikipedia.org/wiki/Bin_packing_problem – Bytemain

奇怪，但实际2D装箱优化

回答

制剂

注

相关问题