生成目标词的最小粘贴数算法

Question

这里有一个算法问题:我们有一个目标词(即“历史”)，我们有一些“标签”：(即“数学”、“英语”、“故事”)。每一张贴纸都有无限个数目。我们希望找到最小数量的贴纸来形成目标单词。

贴纸实际上是一组字母。我们可以把一张贴纸拆成一个字母。对于目标‘历史’，我们可以使用贴纸“故事”和"h，i“(2个字母)从标签”英语“得到”历史“。因此，对于“历史”，使用的最少数量是2(“故事”+“英语”)。

我使用的是Java，所以我认为用HashMap来表示每个字母的出现情况下的目标单词。然后使用回溯来尝试每一种可能组合的贴纸。是否有任何更聪明的方法来解决这个问题，或者可以应用优化？

Answer 1

这听起来像是多集多覆盖问题。

也许，论文集多覆盖和多集多覆盖问题的精确算法的动态规划方法与您相关。

除了动态规划:解决这个问题(需要最优解决方案时)的通常怀疑是卫星解算器和约束规划，它们都有聪明的公式。甚至可能是整数规划。我认为SAT是最有希望的方法，尽管并不是很简单(因为目标中有多个相等的字符；也因为有无限的可用性)。