4

在此处输入图像描述

我试图解决这个问题有点困难。混乱的主要来源是不知道何时移除一个盒子。

这是我的方法：

我逐列查看容器。如果源框的最上面的框是空的，而目标框不是空的，那么我知道要添加那个框。如果反之亦然，我知道要移除顶盒。我认为当两个位置都有一个盒子但不同时我必须交换。但是我的问题出现在某些情况下，删除底部的框会将所有内容向下移动并使其更像目标框。或者可能在中心移除一个或移除两个，一个在底部，一个在中心。我怎么知道什么时候删除一个盒子？我可以删除所有组合，看看哪个组合最接近目的地，但这似乎效率不高。

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

4

2 回答 2

1

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

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

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

于 2014-04-02T15:34:23.863 回答
1

您当然可以一次处理一列。

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

  • case (A): x1is the same as y1: 这是简单的情况，你需要匹配其余的
  • case (B): x1is -and y1is not: 你需要插入所有剩余的y盒子
  • 案例（C）：y1是-和x1不是：您需要删除所有剩余的x框
  • 案例（D）：x1并且y1不是空的而是不同的；在这里你必须选择：（D1）翻转x1并匹配[x2,...]， （D2 ）[y2,...]删除x1并匹配[x2, ...]。[y1, ...]您应该选择（D1）或（D2），具体取决于哪个需要较少的操作。

y1注意：根据规则，插入x和匹配选项（D3）不可[x1,...]用[y2,...]，因为您只能在堆的顶部添加框（案例 B）。

这转化为动态编程（或带有记忆的递归）算法：

int min_moves(int i, int j);

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

要计算min_moves(i, j)，您可以使用min_moves(i+1, j+1)(case A+D1), min_moves(i+1, j)(case D2)。案例 B 和 C 不需要递归，而是直接计算x和y。

于 2014-04-02T15:59:03.647 回答