我一直在试图找到一个由游戏“三重镇”启发的问题的最佳算法。游戏如下：最佳三重镇算法
将对象放置在一个网格中，并且每次制作一组三个对象时，它们会压缩成一个高级对象，放置在最后放置对象的位置。
而且，如果你把这三个B的对象，他们一起再次压缩，形成一个更高级别的对象。
注意：在这些图中的对象的电平被表示为我，B 我，和c 我下标表示对象麻木呃在三个集合中。
为了简化事情，我只考虑你要放置的每个对象的最低级别。
现在我的问题是：
1：是否有一个算法来确定网格区域，使水平x的对象所需的最低金额，定x？
例如，级别a需要1x1，级别b需要1x3，级别c需要1x5。
2：给定网格的尺寸，我们可以找到可实现的最高级别和数量的对象吗？
例如，对于一个2x2的你可以得到2级“a和2级” B的
3：是否有一个算法来寻找对象的最优顺序和位置，以获得尽可能高的级别，给予固定电网？
例如，对于2×2就可以得到（1,1），（1,2），（2,2）
4：给定一个预定的电平x物体的位置，移动的什么组尽量减少制作这个物体所需的空间量？
5：这些算法的最佳复杂性是什么？
更新：
有一件事，我认为是在解决方案的发现突出的是，越来越级别x的项目不能在任何任意位置来完成。
例如：[ _ _ _ _ c]是不可能实现的固定的1乘5格，因为你需要你的最后一个b在第5个地方，因此你的最后一个在第5个地方。所以要放置第一个b：[a _ _ _ _]->[a a _ _ _]->[_ _ b _ _]或[_ a _ _ _]->[_ a a _ _]->[_ _ _ b _]。在这两种情况下，没有足够的空间放置3'a来制作c的最后一个b。
另一件事，我们不能假定任何东西都可以展开到1维网格。随着我的下一点，这变得很清楚。
有趣的东西，我发现：
有一个最小亲近的边界，一个C级的对象可以是在一个维网格。 [_ _ a a a]->[_ _ _ b]->[_ a a a b]->[_ _ _ b b]->[a a a b b]->[_ _ c _ _]。因此，一个1乘5（最优）网格中的c级对象只能在第3个位置创建。
由此可以看出，这是可由任意数量的网格在1中产生的最高等级。通过无限电网采取1：
..._ a a a _ ... -> ... _ a a a b _ ... -> ... _ a a a b b _ ... -> ... _ c _ ...
现在我们设法让另一种C直接旁边：
..._ c a a a _ ... = ... _ c b _ ... or ... _ c _ b _ ... or ... _ c _ _ b _ ...
唯一的选择是..._ c b _ ...因为另作它不可能形成c和b之间的另一个b。我们唯一的选择是阻止我们唯一的方法直接在我们的第一个c旁边创建c，因为它会阻止最后一个c到达那里。因此，在一个维度中，c是我们可以创造的最高水平。换句话说，该问题必须在2维中考虑。
这是一个问题和一半。 :) – biziclop
你有任何中间结果？ –
只是我可以在我的脑海中发现的低网格值。仍然在思考处理它的最佳方式。 – Raufio