复杂的线性规划

Question

我正在尝试通过一种方式解决一个看起来像标准线性规划问题的问题。

我们有一组“短语”作为输入，每个短语都有一个权重。 我们需要选择文本中每个短语的重复次数，以最大化总权重，但要遵守最大字符长度限制。

这似乎是一个简单的线性规划问题，除了一个短语可能是另一个短语的子短语这一事实。 例如，如果您的输入短语包括“foo bar”和“foo”，那么如果您重复短语“foo bar”，您也会重复短语“foo”。 我不知道如何在线性规划模型中处理这个问题。

Answer 1

您还有另一个问题，两个短语的串联可能形成第三个短语。 例如，如果您有

list...4
sting...6
ingrave...7
abcd...5

一个解决方案“listingrave”，则“gain”为 17，而您可以使用“abcd”（“abcdingrave”执行任何操作） >") 只有 12，但对于长度 4，“abcd” 是最佳选择。

不过，这是一个有趣的问题，我认为您需要构建一个自动机来搜索文本中的单词，并且您需要在该自动机中找到一条给定长度的路径，该路径穿过“最甜蜜”的状态（例如，通过给予最多的糖果作为回报）。 我会进一步考虑这一点。

更新：它应该像这样工作：

1. 从 Aho-Corasick 文本搜索算法构建 DFA 从
2. 的起始状态开始，搜索具有最大增益的给定长度的行走（不是路径，即允许重复的边和顶点）外交部。 您可以通过动态编程来实现（从 1 个字符较短的步行构建较长的步行）。

Answer 2

只需重新计算权重即可。 例如：

key = 3
board = 2
keyboard = 5

这将更改为：

key = 3
board = 2
keyboard = 5 + 3 + 2 = 10

如果您这样做，则必须注意包含短语的短语。 您必须确保不这样做：

ey = 7
key = 3 + 7
board = 2
keyboard = 5 + 7 + (3 + 7) + 2

您可以通过在短语长度之后对列表进行排序来避免这种情况。 （最长的第一个）

顺便说一句：这不是一个动态编程问题吗？

Answer 3

也许只使用动态编程并每次重新计算整个过程就可以了。 人们可以使用大量优化来加快速度。 （就像尝试仅重新计算最后一部分一样）我认为速度是合理的。 O(n^2 * m) 左右。

Answer 4

这看起来可以作为背包问题来解决，请参阅http:// en.wikipedia.org/wiki/Knapsack_problem，权重按照 gs 建议定义。