我正在研究一個遊戲，我需要爲特定的句子找到最大的分量。用最重的詞語分句子
假設我有一句話「快速棕色狐狸」，並假設他們的定義體重只有單個單詞：「the」 - > 10，「quick」 - > 5，「brown」 - > 3，「fox」 - > 8
在這種情況下，問題是微不足道的，因爲解決方案包括添加每個單詞的權重。
現在假設我們還加雙字，所以除了上述的話，我們也有「快」 - > 5，「敏捷的棕色」 - > 10，「棕色狐狸」 - > 1
我d想知道哪個單字和雙字組合提供了最大的重量，在這種情況下，它將是「the」，「quick brown」，「fox」我的問題是，除了明顯的暴力方法外，有沒有其他可能的方法來獲得解決方案？不用說，我正在尋找一些最佳的方法來實現這個更大的句子。
謝謝。
您可以查看Integer Linear Program庫，如lp_solve。在這種情況下，您需要最大化分數，並且您的目標函數將包含權重。然後你可以對它進行限制，就像你不能同時擁有「快速棕色」和「棕色」一樣。
對於單詞對齊，這是用於此paper，但您的問題比這更簡單，但您可以瀏覽論文以瞭解如何使用ILP。除了ILP以外，可能還有其他一些算法可以用來解決這個問題，但ILP可以針對小問題以最優和有效的方式解決這個問題。
謝謝，這似乎對我想達到的目標非常有用。將看看這篇論文，並希望瞭解如何將我的問題映射到這種方法。 – Dan 2012-04-04 17:42:17
這感覺就像一個動態編程問題。
我可以想象在每個單詞（即總共k-1個燈泡）之間放置一個燈泡的句子的k個單詞。如果燈泡開啓，這意味着毗連它的單詞是單個短語的一部分，如果它關閉，它們不是。因此，這些燈泡的任何配置都會指示重量的可能組合。當然，許多配置都不可能實現，因爲我們沒有爲他們需要的短語獲得任何分數。所以k-1燈泡意味着我們可以通過最多2 ^（k-1）個可能的答案。我們可以認識到，我們可以在其他計算中重用每個計算的一部分，所以對於（The）（快速）（brown fox ...懶狗）和（the quick） （棕色狐狸...懶惰的狗），我們可以只計算一次（棕色狐狸...懶狗）的最高分數，記住它並在下次看到它時不做任何額外的工作而重新使用它。
在我們開始之前，我們應該首先擺脫只有1個可能值的燈泡（假設我們沒有「棕色狐狸」這個短語或者帶有這個短語的任何更大的短語，那麼光線「棕色」和「狐狸」之間的燈泡總是必須關閉）。每個取下的燈泡將解決方案空間減半。
如果w1，w2，w3是單詞，那麼燈泡將是w1w2，w2w3，w3w4等。所以
Optimal(w1w2 w2w3 w3w4 ...) = max(Optimal(w2w3 w3w4 ...) given w1w2 is on, Optimal(w2w3 w3w4 ...) given w1w2 is off)
（買者如果我們到達那裏，我們有沒有可能解決方案的東西，我們只是回到MIN_INT，事情應該工作了）
我們可以解決這樣的問題，但我們大概可以節省更多時間，如果是聰明的我們接近燈泡的順序。也許首先攻擊中心燈泡可能會有所幫助。我不確定這部分。
因此，句子'快速'的分數是'10 + 5 + 5'？ – mbatchkarov 2012-04-04 16:54:45
首先，句子應該包含所有的單詞，無論是單或雙。在我顯示的情況下，總分將是10 + 10 + 8。請注意，分數適用於單詞或雙字，而不是兩者。 – Dan 2012-04-04 17:44:26