解谜的组合优化
Combinatorial optimization for puzzle solving
下图解释了我的问题
http://i.stack.imgur.com/n6mZt.png
我有数量有限（但相当多）的此类碎片，需要以某种方式堆叠，以使剩余区域尽可能小。这些棋子被锁定在水平轴（时间）上并且具有固定的高度。它们只能堆叠。
剩余区域由堆栈的最大点定义，这取决于选择了哪些棋子。示例图像中的最佳组合是 [1 1 0]。 （其他约束不允许简单的 [0 0 0] 情况）
我唯一的变量是每件作品的二进制文件（是或否）。 objective 比我描述的要复杂一点，但我现在最大的问题是如何制定表达式
Max{Stacked_Pieces} - Stacked_Pieces_Profile
在 objective 函数中。这个表达式的结果当然是一个向量（时间序列），但它会通过其他操作进一步缩减为一个数字。
本质上我的问题是怎么写
Max{A} - A, where A = 1xN vector
在某种程度上与线性（甚至二次）兼容objective。还是我在处理非线性问题？
编辑：这个问题就像一个背包问题，主要区别在于没有背包可以装满。即背包的大小根据所选的部分而变化，并且始终等于堆叠配置文件的顶部
谢谢大家！
据我了解，您基本上可以尝试通过多次迭代将其作为普通背包问题来解决，找到最小值。
现在，找到背包的高度是个问题，这意味着你需要多次迭代。因为需要解背包问题，看某个高度行不行，所以需要多次迭代。
请注意，您确实知道身高的上限和下限。我不确定轮换是否适用，但你可以在这里填补空白：
- Min = max（最小件的最大高度，总尺寸/宽度）
- Max = sum(所有棋子的高度).
基本上解决它就是找到适合所有棋子的最小高度[Min <= x <= Max]。最简单的方法是使用 'for' 循环，但您可以做得更好：
- 尝试最小值、最大值、一半
- if half fits -> max = half;迭代（转到 1）
- 如果一半不合适 -> min = half;迭代（转到 1）
至于解决背包问题，对于每一次迭代，我都会检查所有部件是否仍然可以安装。如果可以加快速度，请使用位掩码和 AND/OR/XOR 操作。
基本上你可以这样做：
- 抢位'x'。填充下一个块
- 检查这是否会导致可能的解决方案
- 找到下一个可以填充的位
请注意，您可能希望使用 C++ 中的内部函数来加快速度。现代 CPU 对此非常擅长。
至于代码：我以前写过一些解决bedlam cube的代码；我很确定，如果你 google 这样做，你会找到一些快速求解器。
祝你好运！
下图解释了我的问题 http://i.stack.imgur.com/n6mZt.png
我有数量有限（但相当多）的此类碎片，需要以某种方式堆叠，以使剩余区域尽可能小。这些棋子被锁定在水平轴（时间）上并且具有固定的高度。它们只能堆叠。
剩余区域由堆栈的最大点定义，这取决于选择了哪些棋子。示例图像中的最佳组合是 [1 1 0]。 （其他约束不允许简单的 [0 0 0] 情况）
我唯一的变量是每件作品的二进制文件（是或否）。 objective 比我描述的要复杂一点，但我现在最大的问题是如何制定表达式
Max{Stacked_Pieces} - Stacked_Pieces_Profile
在 objective 函数中。这个表达式的结果当然是一个向量（时间序列），但它会通过其他操作进一步缩减为一个数字。
本质上我的问题是怎么写
Max{A} - A, where A = 1xN vector
在某种程度上与线性（甚至二次）兼容objective。还是我在处理非线性问题？
编辑：这个问题就像一个背包问题，主要区别在于没有背包可以装满。即背包的大小根据所选的部分而变化，并且始终等于堆叠配置文件的顶部
谢谢大家！
据我了解，您基本上可以尝试通过多次迭代将其作为普通背包问题来解决，找到最小值。
现在，找到背包的高度是个问题，这意味着你需要多次迭代。因为需要解背包问题，看某个高度行不行，所以需要多次迭代。
请注意，您确实知道身高的上限和下限。我不确定轮换是否适用，但你可以在这里填补空白：
- Min = max（最小件的最大高度，总尺寸/宽度）
- Max = sum(所有棋子的高度).
基本上解决它就是找到适合所有棋子的最小高度[Min <= x <= Max]。最简单的方法是使用 'for' 循环，但您可以做得更好：
- 尝试最小值、最大值、一半
- if half fits -> max = half;迭代（转到 1）
- 如果一半不合适 -> min = half;迭代（转到 1）
至于解决背包问题，对于每一次迭代，我都会检查所有部件是否仍然可以安装。如果可以加快速度，请使用位掩码和 AND/OR/XOR 操作。
基本上你可以这样做：
- 抢位'x'。填充下一个块
- 检查这是否会导致可能的解决方案
- 找到下一个可以填充的位
请注意，您可能希望使用 C++ 中的内部函数来加快速度。现代 CPU 对此非常擅长。
至于代码：我以前写过一些解决bedlam cube的代码；我很确定，如果你 google 这样做，你会找到一些快速求解器。
祝你好运！