1

私は、1つのひねりを加えた標準的な線形計画問題のように見える問題を解決しようとしています。

入力として、それぞれに重みがある「フレーズ」のセットがあります。総重量を最大化するために、テキスト内の各フレーズを繰り返す回数を選択する必要がありますが、最大文字長の制限があります。

これは、あるフレーズが別のフレーズのサブフレーズである可能性があるという事実を除けば、単純な線形計画問題のように見えます。したがって、たとえば、入力フレーズに「foo bar」と「foo」が含まれている場合、「foo bar」というフレーズを繰り返すと、「foo」というフレーズも繰り返されます。線形計画モデルでこれを処理する方法がわかりません。

4

4 に答える 4

3

別の問題があります。2 つのフレーズを連結すると、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

これを行う場合、フレーズを含むフレーズを含むフレーズに注意する必要があります。これを行わないようにする必要があります。

ey = 7
キー = 3 + 7
ボード = 2
キーボード = 5 + 7 + (3 + 7) + 2

フレーズの長さの後にリストを並べ替えることで、これを回避できます。(長い順)

ところで:これは動的プログラミングの問題ではありませんか?

于 2009-01-14T09:12:57.987 に答える
0

たぶん、動的計画法のみを使用し、毎回全体を再計算することで機能するでしょう。高速化するために、多くの最適化を使用できます。（最後の部分だけを再計算しようとするような）速度は妥当だと思います。O(n^2 * m) 程度。

于 2009-01-14T09:55:07.560 に答える
-1

これは、ナップサック問題として解決できるようです。gsで提案されているように重みを定義して、http：//en.wikipedia.org/wiki/Knapsack_problemを参照してください。

于 2009-04-06T18:30:48.710 に答える