我一直在試圖找到一個由遊戲「三重鎮」啓發的問題的最佳算法。遊戲如下：最佳三重鎮算法
將對象放置在一個網格中，並且每次製作一組三個對象時，它們會壓縮成一個高級對象，放置在最後放置對象的位置。
而且，如果你把這三個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