1

I'm trying to solve a problem that looks like a standard Linear Programming problem with one twist.

We have as input a set of "phrases" each of which has a weight. We need to choose how many times to repeat each phrase in a text to maximize the total weight, subject to a max character length limitation.

This seems like a straightforward linear programming problem, except for the fact that one phrase could be subphrase of another. So for example if your input phrases include "foo bar" and "foo", then if you repeat the phrase "foo bar", you also repeat the phrase "foo". I don't know how to deal with this in a linear programming model.

4

4 回答 4

3

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

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

那么一个解决方案“ listingrave”有“增益”17，而你可以用“ abcd”（“ abcdingrave”）做的任何事情都只有12，尽管长度为4，“abcd ”是最佳的。

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

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

  1. 从 Aho-Corasick 文本搜索算法构建 DFA
  2. 从 DFA 的起始状态开始，以最大增益搜索给定长度的步行（不是路径，即允许重复的边和顶点）。您可以使用动态编程来做到这一点（从 1 个字符较短的步行构建更长的步行）。
于 2009-01-14T09:41:51.767 回答
0

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

键 = 3
板 = 2
键盘 = 5

这将更改为：

键 = 3
板 = 2
键盘 = 5 + 3 + 2 = 10

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

y = 7
键 = 3 + 7
板 = 2
键盘 = 5 + 7 + (3 + 7) + 2

您可以通过在短语长度之后对列表进行排序来避免它。（最长的优先）

BTW：这不是动态规划问题吗？

于 2009-01-14T09:12:57.987 回答
0

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

于 2009-01-14T09:55:07.560 回答
-1

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

于 2009-04-06T18:30:48.710 回答