問題タブ [dynamic-programming]

動的計画法を使用して加重間隔スケジューリングの問題を解決するプログラムがあります（信じられないかもしれませんが、宿題用ではありません）。私はそれをプロファイリングしました、そして私は私の時間のほとんどをp（...）でMを満たすことに費やしているようです。関数は次のとおりです。

これを最適化する方法を実際に考えることはできません。このアルゴリズムに関する私の知識に基づくと、これは最も時間がかかる可能性が高い場所のようです。しかし、これは私の2番目のOCamlプログラムでもあります。では、これを最適化する方法はありますか？

動的計画法を使用してこれを行う方法が本当にわかりません。問題：テーブルの2つの最大の重なり合わない正方形を見つける必要があります。例：

数字の5と6はそれぞれ行と列の数であり、「R」は予約済みを意味し、「F」は空きを意味します。この場合、最大の正方形は

2番目に大きい（前のものと重複しない）は

これまでのところ、値を2D配列に入れましたが、後で何をすべきかわかりません。0-1ナップザックとLCSを参照しようとしましたが、実際には、テーブルにどの値を入れるべきかわかりません。

私は現在動的計画法を学んでおり、理論はよく知っていますが、新しい問題に対する DP アルゴリズムの設計は依然として困難です。

これは私が今本当に欲しいものです-動的プログラミングによって解決できる問題を提起する本またはウェブサイト。また、説明付きの解決策もあります。数時間頭を悩ませた後でも問題を解決できないかどうかを確認したいと思います。グラフアルゴリズム、動的プログラミングなど、いくつかのカテゴリのアルゴリズムにこの種のものを提供するリソースはありますか?

PS私はTopcoderを検討しましたが、そこにあるソリューションは、効率的なソリューションを実装することを学ぶのにはあまり適していません.

1 と 0 でいっぱいの巨大なファイルで、1 の最大の正方形を見つける必要があります。動的計画法を使用する必要があることはわかっています。私はそれを2D配列に格納しています。最大の正方形を見つけるためのアルゴリズムの助けは素晴らしいでしょう、ありがとう!

入力例:

答え：

これまでの私のコード:

(すでに配列に値が入力されていると仮定します)

そこからどうやって行くの？

オブジェクト指向プログラミングのパターンに関する非常に優れたGoFブック（デザインパターン：再利用可能なオブジェクト指向ソフトウェアの要素）と、このテーマに関するWebの記事やリソースがたくさんあります。

関数型プログラミングのパターン（ベストプラクティス）に関する本（記事、リソース）はありますか？

PythonやRubyのような言語での動的計画法については？

AOPの場合は？

同じ長さ N の 2 つのリスト L1 と L2 があるとします。prodSum を次のように定義します。

L1 がソートされていると仮定して、prodSum(L1, L2) < 事前に指定された値となるような L2 の順列の数を見つけるための効率的なアルゴリズムはありますか?

問題を簡単にするために、L1 と L2 はどちらも [1, 2, ..., N] の整数のリストであると仮定できます。

編集：マナグの答えは、L1とL2が[1、2、...、N]からの整数のリストであると仮定しないと、これは不可能だと確信しました。この制約を前提としたソリューションにはまだ興味があります。

C++でのKnapsackの動的計画法アルゴリズムがあります。関数として実装され、渡された変数にアクセスすると、特定のインスタンスで実行するのに22秒かかりました。これをクラスKnapsackInstanceのメンバー関数にして、そのクラスのデータメンバーである変数を使用させると、実行に37秒かかり始めました。私の知る限り、メンバー関数へのアクセスのみがvtableを通過するため、何が起こっているのかを説明するのに迷っています。

これが関数のコードです

tblは、DPテーブルの1つの列です。最初の列から始めて、最後の列まで進みます。ProfitsWeights変数はペアのベクトルであり、最初の要素は利益で、2番目の要素は重みです。toretは返す値です。

これが元の関数のコードです：-

これは、g++-4.3.2および-O3-DNDEBUGがオンになっているDebianLennyで実行されました。

ありがとう

私は最近、回文に変換するために文字列に (任意の場所に) 挿入する必要がある文字の最小数を計算するよう求めるコンテストの問題を見つけました。

たとえば、文字列 "abcbd" が与えられた場合、"a" の後に 1 つ、"d" の後にもう 1 つ、"a d bcbd a " という 2 つの文字を挿入するだけで回文に変換できます。

これは、文字を最後にのみ追加できることを除いて、同じことを要求する同様の問題の一般化のようです-これには、ハッシュテーブルを使用した O(N) での非常に単純な解決策があります。

この問題を解決するためにレーベンシュタイン距離アルゴリズムを変更しようとしましたが、成功していません。これを解決する方法についてのヘルプ（必ずしも効率的である必要はありません。DPソリューションに興味があるだけです）をいただければ幸いです。

2 つの正の数 N と K を取り、N から K 桁を削除して N を別の数に変換することによって得られる最大の数を計算するアルゴリズム。

たとえば、N=12345 で K=3 の場合、N から 3 桁を削除して得られる最大数は 45 です (他の変換では 12、15、35 になりますが、45 が最大です)。また、N の桁の順序を変更することはできません (したがって、54 は解決策ではありません)。別の例は、N=66621542 で K=3 であるため、解は 66654 になります。

これは動的プログラミングに関連する問題であることはわかっていますが、解決方法がわかりません。これを2日間解決する必要があるので、助けていただければ幸いです。これを解決したくない場合は、解決する必要はありませんが、同様の問題について詳しく読むことができるトリックまたは少なくともいくつかの資料を教えてください.

前もって感謝します。

一般的な動的計画法の問題の目的関数は、目的関数がすべての段階でのアクションと状態の項目の合計であるwiki の動的計画法のように常に定式化できるのでしょうか? それとも、それは単なる特殊なケースであり、一般的な定式化は何ですか?

編集：

「動的計画問題」とは、動的計画法で解ける問題のことです。このような問題は、最適問題と最適構造の性質を持っています。

しかし、少なくとも私にとっては、そのような問題を特定するのは簡単ではない場合があります。おそらく、そのような言葉による説明に慣れていないためです。ベルマン方程式の WIKI ページに出くわしたとき、コスト関数の数学的定式化が何らかの形で役立つと感じました。全体的なコスト/ゲイン関数は、すべての段階からのコスト/ゲインの累積として常に表すことができると思いますか? 蓄積は加算的または乗算的またはその他の可能性がありますか？

私が質問を投稿したとき、数学的最適化を重視した場所で動的計画法について議論する方が適切であることに気付きました。しかし、Stackoverflow.com では、コンピューター アルゴリズムに関する非常に多くの議論が行われています。ですから、ここで質問するのも不当だとは思いませんでした。