問題タブ [dynamic-programming]

メモ化プロセスを処理できる以下のようなクラスを作成することは「良い習慣」ですか? メモ化の利点は非常に大きいため (この例のように、関数呼び出しが 501003 秒から 1507 秒に減少し、コンピューターの CPU 時間が 1.409 秒から 0.006 秒に減少する場合もあります)、このようなクラスが役立つと思われます。

ただし、の使用に関する否定的なコメントしか読んだことがありませんeval()。このアプローチが提供する柔軟性を考えると、この使用法は許されますか?

これにより、副作用が失われるという犠牲を払って、返された値を自動的に保存できます。ありがとう。

の値があり、ドル紙幣を使用Nして合計する方法がいくつあるかを計算する必要がある問題を考えてみましょう。N[1,2,5,10,20,50,100]

従来の DP ソリューションを検討してください。

合計された部分の順序は有効になりません。たとえば、comb(4)5 つの結果が得られます[1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2]が、実際には 3 つ[2,1,1],[1,2,1],[1,1,2]の結果があります (すべて同じです)。

この問題を計算するための DP イディオムは何ですか? (すべての可能なソリューションを生成し、重複を削除するなどの非エレガントなソリューションは歓迎されません)

この問題は、 SkienaによるThe AlgorithmDeisgnManualの動的計画法の章から出てきます。

雑誌から切り抜きを貼り付けて、特定の文字列を生成できるかどうかを判断するアルゴリズムを提供します。任意の文字位置について、ページの裏側にある文字とその位置を識別する関数が与えられます。

私はこれをバックトラックで解決しましたが、動的計画法の章にあるので、私には理解できない再発があるに違いないと思います。誰かが私にヒントを与えることができますか？

文字列を単語に分割する正しい方法は何ですか？（文字列にはスペースや句読点は含まれていません）

例：「stringintowords」->「StringIntoWords」

ここで使用するアルゴリズムを教えてください。

！更新：この質問は好奇心のためだけだと思う​​人のために。このアルゴリズムは、ドメイン名（ "sportandfishing .com"-> "SportAndFishing .com"）をカメラ化するために使用でき、このアルゴリズムは現在、aboutusdotorgによってこの変換を動的に行うために使用されています。

任意のペグソリティアボード構成を考えると、「ゲーム終了」の位置になる一連の動きを計算するための最も効率的な方法は何ですか。

たとえば、標準の開始位置は次のとおりです。

そして、「ゲーム終了」の位置は次のとおりです。

ペグソリテールについて詳しくは、ウィキペディアをご覧ください。「英語ボード」のバリエーションを検討しています。

P4 3Ghzのように、妥当なコンピューター上で、わずか数秒で任意の開始ボードを解決できると確信しています。

現在、これが私の最善の戦略です。

C++ プログラムで使用する LCS アルゴリズムの (空間) 効率的な実装を探しています。入力は、整数の 2 つのランダム アクセス シーケンスです。
私は現在、LCS に関するウィキペディアのページから動的プログラミング アプローチを使用しています。ただし、それはメモリと時間で O(mn) の動作をし、より大きな入力に対してメモリ不足のエラーが発生して死にます。
Hunt-Szymanski、Masek、Paterson など、メモリ使用量を大幅に改善する Hirschberg のアルゴリズムについて読んだことがあります。これらを実装するのは簡単ではないので、既存の実装で自分のデータで試してみたいと思います。そのようなライブラリを知っている人はいますか？テキストの差分ツールはかなり一般的であるため、オープンソースのライブラリがいくつかあるはずだと思いますか?

エントリがすべて 0 または 1 の配列 M[1..m,1.. n] で表される mXn ビットマップが与えられたとします。すべて 1 のブロックは、M[i .. i0, j .. j0] で、すべてのビットが 1 に等しい. M 内のすべてが 1 で面積が最大のブロックを見つける効率の良いアルゴリズムを説明、解析してください。

動的プログラミング ソリューションを作成しようとしています。しかし、私の再帰アルゴリズムは O(n^n) 時間で実行され、メモ化の後でも O(n^4) 未満に下げることは考えられません。誰かがより効率的な解決策を見つけるのを手伝ってくれますか?

エントリがすべて 0 または 1 の配列 M[1..m,1.. n] で表される mXn ビットマップが与えられたとします。すべて 1 のブロックは、M[i .. i0, j .. j0] で、すべてのビットが 1 に等しい. M 内のすべてが 1 で面積が最大のブロックを見つける効率の良いアルゴリズムを説明、解析してください。

動的プログラミング ソリューションを作成しようとしています。しかし、私の再帰アルゴリズムは O(n^n) 時間で実行され、メモ化の後でも O(n^4) 未満に下げることは考えられません。誰かがより効率的な解決策を見つけるのを手伝ってくれますか?

私はこの問題のための合理的なアルゴリズムを考え出そうとしています：

あなたがたくさんのボールを持っているとしましょう。各ボールには少なくとも1つの色がありますが、多色にすることもできます。各ボールにも番号が付いています。それぞれが1色だけの箱もたくさんあります。目標は、ボックス内のボールの数の合計を最大化することであり、唯一のルールは次のとおりです。

• ボックスにボールを配置するには、少なくともボックスの色が含まれている必要があります
• 各ボックスに入れることができるボールは1つだけです。

たとえば、青と緑のボールを青いボックスまたは緑のボックスに入れることはできますが、赤いボックスに入れることはできません。

実行時間の点で大いに役立ついくつかの最適化を考え出しました。たとえば、ポイント値の降順でボールを並べ替えることができます。次に、最大数から最小数に進むにつれて、ボールの色が1つだけで、その色を含む高得点のボールが他にない場合は、そのボックスに入れることができます（したがって、そのボックスとそのボールを残りの組み合わせ）。

このタイプの問題にはある種の動的アルゴリズムがあるのか​​、それとも巡回セールスマン問題に変装しているだけなのか、私はただ興味があります。最大でX色あることを知っていれば役に立ちますか？どんな助けでも大歓迎です。ありがとう！

編集-簡単な例を次に示します。

ボール：

• 赤いボール1個-5ポイント
• 青いボール1個-3ポイント
• 緑/赤のボール1個-2ポイント
• 緑/青のボール1個-4ポイント
• 赤/青のボール1個-1ポイント

ボックス：

• 赤1個
• 青1個
• 1グリーン

最適なソリューション：

• 赤いボックス内の赤いボール
• 青いボックスの青いボール

• 緑のボックスに緑/青のボール

  合計値：12ポイント（5 + 3 + 4）

10種類のゲームをプレイしているとしましょう。ゲームごとに、勝つ確率、引き分けの確率、負ける確率を知っています (ゲームごとに確率は異なります)。

これらの値から、X ゲームに勝つ確率、X ゲームに負ける確率、X ゲームに引き分けになる確率 (X = 0 ～ 10) を計算できます。

10 ゲームすべてをプレイした後、 Wゲームに勝ち、 Tゲームで同点になり、 Lゲームに負ける確率を計算しようとしています... O(3^n) よりもうまくいくことを願っています。たとえば、7 勝 2 敗 1 引き分けの確率は?

何か案は？ありがとう！

編集 - ゲームが 2 つしかない場合のデータの例を次に示します。

ゲーム 1:

• 勝率: 23.3%
• 同率：1.1%
• 負け: 75.6%

ゲーム 2:

• 勝率: 29.5%
• 同点：3.2%
• 負け: 67.3%

これに基づいて、次の 2 つのゲームをプレイした後の確率を計算できます。

• 0勝：54.0%
• 1勝：39.1%
• 2勝：6.9%

• 0同点：95.8%
• 1同点：4.2%
• 2 ネクタイ: 0.0%

• 0 損失: 8.0%
• 1敗：41.1%
• 2敗：50.9%

これらの数字に基づいて、W勝、T引き分け、L敗の確率を見つけるための一般的な公式はありますか? 考えられる結果 (WLT) は次のようになります。

• 2-0-0
• 1-1-0
• 1-0-1
• 0-1-1
• 0-2-0
• 0-0-2