堆箱子算法

Question

我在解决这个问题时遇到了一些困难。主要的混淆来源于不知道何时删除一个方框。

我的方法如下：

我逐列查看容器。如果原始方框的最上面的方框为空，目标方框不为空，则我知道要添加该方框。如果相反，则我知道要删除顶部方框。当两个位置都有方框但不同的时候，我认为我必须进行交换。然而，我的问题出现在某些情况下，例如在底部删除一个方框将使所有内容向下移动并更接近目标方框。或者也许是在中间删除一个或删除两个，一个在底部，一个在中间。我如何知道何时删除方框？我可以删除所有组合并查看哪个最接近目标，但那似乎不太有效率。

我也可能认为这是一个明显的动态编程问题，超出了我的能力范围。任何帮助都将不胜感激。

- user1879789

---

我完全不是算法方面的人（那不是我的最佳课程，而且那是几年前的事了）。我只是想说，看到一个作业问题并不仅仅是原始问题的转储，没有尝试显示他们在发布之前是否尝试过任何东西或甚至考虑过它，这真是让人耳目一新，因为作业问题通常看起来都是这样的。 :) - neminem

哦，谢谢你！我尽可能地让那些在这里助人为乐的人们更容易理解。 - user1879789

Answer 1

您已经将问题简化为一次考虑一列，所以让我们从那里开始。

不要考虑在一列中可以发生的特定操作，让我们看一下整个过程。 最初，我们有了给定的列。 最后，我们得到了结果列。 给定列在结果列中剩下什么？ 它是给定列的子序列（因为我们可以从任何位置移除一个盒子），被转移到结果列的前缀中（“前缀”位于“底部”，因为我们只能在最初的基础上添加新盒子）。

自然地，我们想要最大化这个序列（取决于您查看的位置，可以是子序列或前缀）的长度。 这看起来像一个动态规划问题，类似于编辑距离或最长公共子序列。 也许您想要从这一点开始自己解决细节。 祝你好运！

- Gassa

---

谢谢，这就是我需要的。 - user1879789

Answer 2

你当然可以逐列工作。

然后，将列 [x1，x2，x3，...] 转换为列 [y1，y2，y3，...] 有几种情况：

• 情况（A）：x1 与 y1 相同：这是简单的情况，您需要匹配其余部分
• 情况（B）：x1 是 - 而 y1 不是：您需要插入所有剩余的 y 方块
• 情况（C）：y1 是 - 而 x1 不是：您需要删除所有剩余的 x 方块
• 情况（D）：x1 和 y1 都不为空但不同；在这里，您必须选择：（D1）翻转 x1 并将 [x2,...] 与 [y2,...] 匹配，（D2）删除 x1 并将 [x2, ...] 与 [y1, ...] 匹配。根据哪个需要更少的操作，您应该选择（D1）或（D2）。

注意：根据规则，选项（D3）在将y1插入x并将[x1，...]与[y2，...]匹配时不可用，因为您只能在堆栈顶部添加框（情况B）。

这在动态编程（或递归记忆化）算法中进行翻译：

int min_moves(int i, int j);

你需要计算将列 x[i], x[i+1], ... 对齐到列 y[j], y[j+1], ... 所需的移动次数，其中 x 和 y 是从文件中读取的两个清单的原始内容，假设对于任何 i>m，x[i] 和 y[i] 都为 -。

要计算 min_moves(i, j)，您可以使用 min_moves(i+1, j+1)（情况A+D1），min_moves(i+1, j)（情况D2）。情况B和C不需要递归，但是是对 x 和 y 的直接计算。

- 6502