問題タブ [dynamic-programming]

PHPのナップサック問題などの動的計画法の問題を解決する実際のコードを見つけることができるリソースはありますか？

理論がよくわからないので、自分でコードを分析したいです。そして、私はグーグルでコードを見つけることができません。

どうもありがとうございます。

is there a DP approach for the n-puzzle problem

thanks all, appreciate that...

rajan

これは基本的に次の複製です。

文字列を単語に分割する方法。例: "stringintowords" -> "文字列を単語に変換"?

それにもかかわらず、私は次のような関数を使用しています: public int Word(x) {code}、文字列 x の場合、整数 (+ve または -ve) を返します。その整数は、特定の単語に対するパーティション分割の良し悪しを示します。 . 最大数を与える組み合わせを返す必要があります。

このために私が考えたのは、 i と j が単語の長さである table(i,j) を作成し、次のように表を tern に記入することです。

それにもかかわらず、一体どのようにして最適解を取得できるのでしょうか (再帰的な方法で?)

助けていただければ幸いです。

編集: 最適なパスは、word(x) 関数の合計が最も高いパスです。つまり
、 path(1,3)=10 、 (3,6)=20 、 (6,7)=1 、および
パス (1,1)=0 、(2,5)=12、(5,7)=-1
の場合、1 番目のパスの合計 > 2 番目

EDIT2：この質問は、長時間の作業の後に私が回答したことをすべての人に知ってもらいたいのですが、解決策が得られないことを気にしないでください。

乾杯！：）

私はこの問題に取り組んでいます:

X = {x1, x2 ,…, xn}部分和問題は、一連のn整数と別の整数を入力として受け取りますK。問題は、要素の合計が になるサブセットX'が存在するかどうかを確認し、存在する場合はそのサブセットを見つけることです。たとえば、サブセットの合計が であるため、答えはです。実行時間が少なくとも である Subset Sum のアルゴリズムを実装します。XKX = {5, 3, 11, 8, 2}K = 16YESX' = {5, 11}16O(nK)

複雑さに注意してくださいO(nK)。動的計画法が役立つと思います。

指数時間アルゴリズムを見つけましたが、役に立ちません。

誰かがこの問題を解決するのを手伝ってくれますか?

問題は次のとおりです。

1. 「いい」について

   1) 「ab」いいですね

   2) A はいいね => "a"+A+"b" はいいね

   3) A と B がいい => A+B がいい

2. 「～」について

   1) 「アブ」～「アブ」

   2) A~B => "a"+A+"b"~"a"+B+"b"

   3) A~B および C~D => A+C~B+D および A+C~D+B

現在、セット S を形成する 'a' と 'b' の最大 1000 個の文字列があり、すべての要素がナイスでなければならず、ペア (A,B) のいずれも A~B を保持しない S の最大のサブセットを見つけます。カーディナリティを出力します。

前に見た問題とは異なる sth があります: A+B+C+D~A+C+B+D~B+D+A+C but A+B+C+D~B+D+A+C保持しません。

私にとって2つの困難：

1. S1～S2かどうかの確認方法
2. すべてのペアの "~" がわかっている場合、カーディナリティを見つけるにはどうすればよいですか

詳細: https://www.spoj.pl/problems/ABWORDS/

OK、ここで私がしなければならないことです

MCI (Mammoth Cakes Incorporated) の従業員として、非常に大きな層状のバースデー ケーキを作成するのがあなたの仕事です。レイヤード バースデー ケーキは、小さな円形のケーキの層を取り、それらを積み重ねることによって作られます。

仕事を遂行するには、さまざまなサイズのレイヤーが目の前を通過する間、大きなベルトコンベアの前に立ちます。気に入ったものを見つけたら、コンベア ベルトから外してケーキに追加できます。

次のルールに従う限り、ケーキに好きなだけレイヤーを追加できます。

レイヤーがケーキに追加されると、移動できなくなります。（アイシングが台無しになります。）したがって、レイヤーはケーキの上部にのみ追加できます.

各レイヤーは一度だけあなたの前を通過します。あなたはそれを取るか、それを残すことができます。それを取る場合は、ケーキの上に追加する必要があります。放っておくと、ベルトコンベアを下っていき、二度と戻りません。

ケーキの各層は、少なくとも下の層と同じくらい小さくする必要があります。小さいレイヤーの上に大きいレイヤーを配置することはできません。

コンベアベルトを下って来る層の直径（インチ単位）が事前に通知されます。あなたの仕事は、これらのレイヤーを使用して、可能な限り高いケーキを作成することです。たとえば、次のリストがコンベア ベルトを下って来る層の直径を表しているとします: 8 16 12 6 6 10 5

ケーキの最初の層 (直径 8 インチ) を使用するとします。つまり、2 番目のレイヤーを使用することはできません (サイズ 8 インチ、および 16 インチ > 8 インチのレイヤーが既にあるため)。同様に、3 番目のレイヤーを取得することはできませんが、4 番目のレイヤーを取得することはできます (6 インチ < 8 インチであるため)。

それに続いて、5 番目のレイヤーを使用することもできます (ルールは、一番上のレイヤーを大きくすることはできず、同じサイズにすることができます)。この方法で 4 層の高さのケーキを作成できます: 8 6 6 5 ただし、最初の層を続けて 2 番目の層から始めると、高さ 5 のケーキを作成できます。 16 12 6 6 5

プログラムは、1 行に 1 つずつ、複数の入力セットを処理します。各行は整数 N で始まり、コンベア ベルトに到着する順序でケーキ層のサイズを表す N の正の整数が続きます。N は常に負でない整数、0 N 100,000 です。各レイヤーの直径は 1 ～ 100,000 です。N = 0 が入力の終わりを示す行

質問: ケーキの一番高い層を見つけてください

これまでに書いたものは次のとおりです。

講師がクラスでこの質問をしました：[質問]

n個の整数のシーケンスが配列A[1..n]に格納されます。Aの整数aは、Aにn / 2回以上出現する場合、多数派と呼ばれます。

O（n）アルゴリズムは、次の観察に基づいて過半数を見つけるために考案できます。元のシーケンスの2つの異なる要素が削除された場合、元のシーケンスの過半数は新しいシーケンスの過半数のままです。この観察結果を使用するか、そうでない場合は、プログラミングコードを記述して、O（n）時間で大部分が存在する場合はそれを見つけます。

この解決策が受け入れられた[解決策]

提供されているソリューションが動的ソリューションであることがわかりません。そして、その言葉遣いに基づいて、彼がそのコードをどのように引き出したかはわかりません。

これは難しいアルゴリズムの問​​題です：

リストを2つの部分（合計）に分割し、それらの合計が（最も）互いに最も近いものにします

リストの長さは1<=n <= 100であり、それらの（数）の重みは1 <= w<=250です。

例：23 65134 32 95123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

アルゴリズムはありますが、すべての入力で機能するわけではありません。

1. 初期化。リストlist1=[]、list2 = []
2. 要素の並べ替え（指定されたリスト）[23 32 34 65 95123134]
3. 最後の1つをポップ（最大1つ）
4. 違いの少ないリストに挿入

実装：list1 = []、list2 = []

1. 134挿入リスト1を選択します。list1 = [134]
2. 123挿入リスト2を選択します。list1に挿入すると、差が大きくなるためです
   。3. 95を選択し、list2を挿入します。sum（list2）+ 95-sum（list1）が小さいためです。

等々...

これは、動的計画法に関連する別のアルゴリズムの問​​題です。

ここに問題があります：

各行と列で1つを選択するように、指定された行列の最小合計を見つけます

例えば ​​：

3 4 2

8 9 1

7 9 5

最小のもの：4 + 1 + 7

解決策はネットワークフロー（最大フロー/最小カット）だと思いますが、それほど難しくはないはずです

私の解決策：nに分離list [column]、column1、column2 ... column n

次に、開始点（S）->列1->列2-> ...->列n->（E）終了点で、最大フロー/最小カットを実装します

これは、指定された行列 (mxn) で最大の L(チェスの馬 - 4 アイテム) の合計を見つける別の動的計画問題です。

例えば ​​：

1 2 3

4 5 6

7 8 9

L : (1,2,3,6)、(1,4,5,6)、(1,2,5,8)、(4,5,6,9) ...

最大の合計は sum(L) = sum(7,8,9,6) = 30

最適解の O(複雑さ) は?

この問題のようです（最大合計の部分行列）

1. すべての項目が正であると言う

2. ポジティブにもネガティブにも

どんなアイデアでも大歓迎です！