我被困在解决这个问题上了。造成混乱的主要原因是不知道什么时候该移除一个盒子。
我的方法是：
我一列一列地看集装箱。如果原语框的顶部大部分框是空的，而目标框不是空的，那么我知道要添加该框。如果顶部的盒子反过来的话，我知道要把它移除。我认为，当两个位置都有一个盒子，但又不同的时候，我必须交换。然而，我的问题是，在某些情况下，移除底部的框会将所有东西向下移动，使其更像目标框。或者可能移除中间的一个，或者移除两个，一个在底部，一个在中间。我怎么知道什么时候取下一个盒子？我可以删除所有的组合，看看是什么使它最接近目的地，但这似乎没有效率。
我也可能认为这是一个明显的动态规划问题，在我脑海中浮现。如能提供任何帮助，将不胜感激。
回答 2
Stack Overflow用户
发布于 2014-04-02 07:34:23
Stack Overflow用户
发布于 2014-04-02 07:59:03
当然，您可以一次工作一个列。
然后，要将列[x1, x2, x3, ...]转换为列[y1, y2, y3, ...]，有几种情况：
- case (A)：
x1与y1相同:这是很简单的情况，您需要匹配其余的 - 案例(B)：
x1是-，y1不是:您需要插入所有剩余的y框 - 案例(C)：
y1是-，x1不是:您需要删除所有剩余的x框 - case (D)：
x1和y1不是空的，而是不同的；在这里您必须选择：(D1)翻转x1和匹配[x2,...]与[y2,...]，(D2)移除x1和匹配[x2, ...]与[y1, ...]。您应该选择(D1)或(D2)，这取决于哪种操作需要更少的操作。
注意:根据规则，在D3中插入y1并将[x1,...]与[y2,...]匹配的选项( x )是不可用的，因为您只能在堆的顶部添加框(案例B)。
这在动态规划(或递归与回传)算法中转换为：
int min_moves(int i, int j);您需要计算将列x[i], x[i+1], ...对齐到列y[j], y[j+1], ...的移动次数，其中x和y是从文件读取的两个清单的原始内容，假定x[i]和y[i]是任何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上计算。
https://stackoverflow.com/questions/22815796
复制
腾讯云开发者
