algorithm - 具有最大权重的单词分区

Question

我正在开发一款游戏，我需要找到特定句子的最大权重。

假设我有一个句子“the quick brown fox”，并假设单词和双词都具有定义的权重:“the”-> 10，“quick”-> 5，“brown”-> 3，“fox” -> 8，“快速” -> 5，“快速棕色” -> 10，“棕色狐狸” -> 1

我想知道哪种单双词组合提供的权重最大，在本例中为“the”、“quick brown”、“fox”(权重 = 28)

有人告诉我这个问题可以通过线性规划来解决，但我看不出如何实现这种方法。具体来说，我不知道如何表达问题的约束，在这种情况下，一些双词不能与包含的单个词组合(即“快速”不能与任何一个组合“the”或“quick”)

有人可以就如何解决这个问题提供一些指导吗？我不是该领域的专家，对 Simplex 的工作原理有一些基本的了解(从学校回来)，但我缺乏关于如何为此类问题建模的知识。

此外，任何其他方法(不涉及线性规划或蛮力)也将受到欢迎。

谢谢。

Answer 1

假设组合只有单双字:

int single[n];//if we choose i-th word : single[i]
int doubles[n];//if we choose the i-th and i+1-th word as a combination : doubles[i], the last word has the same value for it's single and doubles

int dp[n+2];//dynamic programming
dp[n] = dp[n+1] = 0;//bottom up

for(int i=n-1;i>=0;i--)
{
    dp[i]=max(dp[i+1]+single[i],dp[i+2],double[i];
}
//the maximum value is dp[0]