algorithm - 用剪下的杂志人物生成一条消息(采访问题)

Question

此问题出自 Skiena 的 The Algorithm Deisgn Manual 中的动态规划章节。

Give an algorithm to determine whether you can generate a given string by pasting cutouts from a magazine. You are given a function that will identify the character and its position on the reverse side of the page for any given character position.

我用回溯解决了这个问题，但因为它在动态规划章节中，我认为一定有一个我无法弄清楚的重复。谁能给我一个提示？

Answer 1

你可以用最大二分匹配来解决它。

给定字符串的每个字符 L 构成左集。 (注意，如果字符串有重复字符，则重复字符)。

杂志的每对字符 (R1,R2) 形成右集。

L 连接到 (r1,r2) 当且仅当 L=R1 或 L=R2。

在结果图中找到最大匹配。如果所有左顶点都是匹配的一部分，你就有答案了。否则，这样的字符串是不可能的。

参见 Maximum Bipartite Matchings对于算法。

虽然不确定这是否是最佳选择，但很抱歉没有完全按照要求回答。