最大分量的文字分區

我正在開發一款遊戲，我需要爲特定語句找到最大分量。最大分量的文字分區

假設我有一句「快速棕色狐狸」，並假定他們的定義重量的單詞和雙重單詞：「the」 - > 10，「quick」 - > 5，「brown」 - > 3，「fox 「 - > 8，」快速「 - > 5，」快速棕色「 - > 10，」棕色狐狸「 - > 1

我想知道單字和雙字的哪個組合提供最大的權重，在這種情況下，它會是「the」，「quick brown」，「fox」（weight = 28）

我已經被告知這個問題可以通過線性編程來解決，但我沒有看到如何實現這樣的方法。具體而言，我不知道如何表達問題的約束，在這種情況下，一些雙重單詞不能與包含單個單詞的單詞組合（即「快速」不能與任何「the」或「quick」）

有人可能會提供一些指導方法來解決這個問題嗎？我不是該領域的專家，對Simplex如何工作（退學）有一些基本的瞭解，但我缺乏關於如何對這類問題建模的知識。另外，任何其他方法（不涉及線性規劃和蠻力）也會受到歡迎。

謝謝。

來源

2012-04-11 Dan

假設該組合僅由單，雙字：

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]

來源

2012-04-11 17:30:00

爲您的樣品問題的蠻力方法涉及可能的組合 - 讓我們看看我們是否能夠降低下來。爲了便於學習，讓我們的映射變量：

the quick brown fox -> (a1, a2, a3, a4) 
the quick -> b1 
quick brown -> b2 
brown fox -> b3

凡a3=True意味着我們使用的「棕色」。由此，我們可以構建一套規則。例如，b3不能一起使用a3或a4：

(a1:b1)  (b1:a1,a2) 
(a2:b1,b2) (b2:a2,a3) 
(a3:b2,b3) (b3:a3,a4) 
(a4:b3)

現在從陣列S=[a1=0,a2=0,...,b3=0]開始通過變量的組合遞歸步驟，早期修剪分支如果它違反了我們的規則之一。如果我們到達一個葉節點，輸出對應於變量的權重，並保持它是否是迄今爲止最大的。這可能不是最有效的答案，但它確實可以減少組合。

來源

2012-04-11 17:43:23 Hooked

撥打電話BiggestWeight(i)從i位置到n-1這個字的子問題，其中n是字數。

你的問題是找到BiggestWeight(0)。
基座情況是BiggestWeight(n)，等於0，由於字的列表爲空，和BiggestWeight(n-1)，等於weight(n-1)，因爲只有一個用於與一個字的列表的選擇。
子問題之間的關係是： BiggestWeight(i) = max(weight(i)+BiggestWeight(i+1), pairWeight(i,i+1)+BiggestWeight(i+2)) 因爲i個字或者是一個單字，或第一雙字的。

因此，如果值存儲在尺寸n+1的表，其結果可在O(n)找到。

來源

2012-04-11 18:57:55 galath

您可以在這裏非常有效地使用DP。

設F是最大權重函數，並讓句子是W1，W2，W3 ...周

令G（[W1，W2，...]）返回組合的字典重量。（[w1 w2 w3 ... wk]）= Max（G（[w1]）+ F（[w2 w3 ... wk]），G（[w1，w2]）+ F（[w1 w2 w3 wk] w3 w4 ... wk]）...）

來源

2012-04-11 19:07:46 ElKamina

最大分量的文字分區

回答

相關問題