問題タブ [dynamic-programming]

従来のRLEアルゴリズムは、数字を使用してデータを圧縮し、数字に続く文字がその位置のテキストに表示される回数を表します。例えば：

AAABBAAABBCECE => 3A2B3A2B1C1E1C1E

ただし、上記の例では、その方法により、圧縮テキストによって使用されるスペースがさらに多くなります。数字を使用して、数字に続く部分文字列が特定のテキストに表示される回数を表すことをお勧めします。例えば：

AAABBAAABBCECE => 2AAABB2CE（ "AAABB"を2回、次に "CE"を2回）。

さて、私の質問は、この方法を使用して、最適なRLEの最小文字数を見つける効率的なアルゴリズムをどのように実装できるかということです。ブルートフォースメソッドは存在しますが、もっと高速なものが必要です（最大でO（長さ²））。おそらく、動的計画法を使用できますか？

これは、TSP (巡回セールスマン問題) の動的プログラミング疑似コードです。最適な部分構造は理解できましたが、赤い括弧内のコードが何をするのかわかりません。

私は誰かに実際のコードを書くように頼んでいるわけではありません。何が起こっているのかについての説明が必要なので、自分でコードを書くことができます....ありがとう:)

ここに疑似コードのリンクがあります。ここにアップロードできませんでした。 http://www.imagechicken.com/viewpic.php?p=1266328410025325200&x=jpg

可能な値のセットと「桁」の数が与えられた場合、一意で順序付けられていない値のグループをすべて見つけたいと考えています。たとえば、A、B、C のアルファベットがあるとします。3 桁のすべての組み合わせは次のようになります。

私が解決しようとしている特定の問題は、もう少し単純です。F# の演習として BlackJack ゲームをやっています (これについては以前に投稿しました)。私がハンド値を計算する方法は、カードの可能な値のリストのリストを使用することです。エースを除くすべてのカードはリストに 1 つのアイテムを持っていますが、エースは 1 または 11 のいずれかです。その投稿で思いついた実装は、多くの冗長性を生成します。たとえば、3 つのエースは のようなリストを作成します[3; 13; 13; 13; 23; 23; 23; 33]。今、私は最終的なリストを取得して実行していDistinct()ますが、ちょっとしたハックのように感じます.

これをすべてまとめると、エースの潜在的な値 (1、11) がアルファベットを構成し、手のエースの数によって桁数が決まります。この場合、アルゴリズムで次のパターンを考え出す必要があります。

ここで動的プログラミングが登場する可能性があることを何かが教えてくれますが、適切な用語が不足しているため、少し立ち往生しています。どんな助けでも大歓迎です。

編集

価値があるのは、特定の問題に対するより単純な解決策があることを私は認識していますが、関数型プログラミングの演習であるため、一般性が私の目標の 1 つです。

この有名な dp 問題を多くの場所で見つけましたが、解決方法がわかりません。

n 種類の長方形の 3-D ボックスのセットが与えられます。ここで、i^ 番目のボックスは高さ h(i)、幅 w(i)、深さ d(i) (すべて実数) です。できるだけ高さのあるボックスのスタックを作成したいのですが、ボックスを別のボックスの上にスタックできるのは、下のボックスの 2 次元ベースの寸法が 2 次元ベースの寸法より厳密に大きい場合だけです。ハイボックスのDベース。もちろん、ボックスを回転させて、任意の側面がベースとして機能するようにすることもできます。同じタイプのボックスの複数のインスタンスを使用することもできます。

この問題は複雑すぎて、手順を理解できません。3Dなので、高さ、幅、奥行きの3つのシーケンスを取得します。しかし、3次元を交換することが可能であるため、問題は私にとってより複雑になります. スワッピングがない場合の問題を解決する手順と、スワッピング時にそれを行う方法を誰かが説明してください。私はその問題に疲れました。ですから、誰かが解決策を簡単に説明してください。

M 個の 2 進数の配列があり、それぞれの状態は「0」または「1」です。数値の状態を変更するには、いくつかの手順を実行できます。各手順では、正確に N 個の連続した数値の状態を変更できます。もちろん、数値 M、N、およびメンバーを含む配列が与えられると、すべての 2 進数を 1 つの状態 (1 または 0) に変換するために必要な最小ステップ数を計算しようとしています。

M = 6 および N = 3 で、配列が 1 0 0 1 0 0 の場合、解は 2 になります。配列を 111000 に変換し、最後の 3 つの (N) 0 を 1 に反転します。

整数の配列A[i]（i> 1）は、次のように定義されます。要素A [k]（k> 1）は、A [k-1]より大きい最小の数値であり、その桁の合計は次のようになります。は、数値4 *A[k-1]の桁の合計に等しくなります。

指定された最初の要素A[1]に基づいて、この配列のN番目の数を計算するプログラムを作成する必要があります。

入力：標準入力の1行には、A [1]（1 <= A [1] <= 100）とN（1 <= N <= 10000）の2つの数字が1つのスペースで区切られています。

出力：標準出力には、定義されたシーケンスのN番目の数値である単一の整数A[N]のみが含まれている必要があります。

入力：7 4

出力：79

説明：配列の要素は次のとおりです：7、19、49、79...そして4番目の要素は解です。

与えられた数に対してA[k]がその桁の合計を計算し、問題で述べられているようにA [k-1]より大きい最小の数を見つける別の関数をコーディングしてこれを解決しようとしましたが、成功しませんでした。最初のテストはメモリ制限のために失敗し、2番目のテストは時間制限のために失敗しました、そして今私はこれを解決する方法について考えられる考えがありません。ある友人が再帰を提案しましたが、それを設定する方法がわかりません。

何らかの形で私を助けてくれる人は誰でも書いてください。また、この問題を解決するために再帰/DPを使用することについてのいくつかのアイデアを提案してください。ありがとう。

2 つの任意のポリゴンをパッキングする際に問題があります。つまり、2 つの任意のポリゴンがあります。この多角形に外接する長方形の面積が最小の場合、この多角形のそのような配置を見つける必要があります (回転と移動を行うことができます)。

私は、これが NP 完全問題であることを知っています。この問題を解決するための効率的なアルゴリズムを選択したいと考えています。No-Fit-Polygon アプローチを探しています。しかし、任意の 2 つのポリゴンの NFP を見つけるための単純で明確なアルゴリズムはどこにも見つかりませんでした。

私は整数のセットを持っています。動的計画法を使用して、そのセットの最長増加サブシーケンスを見つけたいです。

アルゴリズムコースの古いメモをいくつか確認していますが、動的計画法の問題は少し注意が必要です。いくつかの金種x1、x2、... xnのコインが無制限に供給され、ある値Xを変更したいという問題があります。動的プログラムを設計して、Xの変更が可能かどうかを判断しようとしています。作られるかどうか（コインの数を最小化しない、またはどのコインを返すか、正誤問題）。

私はこの問題についていくつか考えました、そしてそれが次のようなものであるところでこれを行う再帰的な方法を見ることができます...

これを動的プログラムに変換することは、私にはそれほど簡単ではありません。どうすればこれにアプローチできますか？

入力：正と負の要素を持つ2次元配列NxN-行列-。

出力：可能なすべての部分行列の中でその合計が最大になるような任意のサイズの部分行列。

要件：アルゴリズムの複雑さはO（N ^ 3）である必要があります

歴史： Algorithmist、Larry、およびKadaneのAlgorithmの修正の助けを借りて、私は問題を部分的に解決することができました。これは、以下のJavaでの合計のみを決定することです。マトリックスの境界、つまり左上隅、右下隅、つまり下のRubyを決定するという、残りの問題を解決することができたErnesto
に 感謝します。