問題タブ [recursive-backtracking]

nバックトラッキングコードがいくつかの解決策を見つけたかどうかを確認する必要がある Python の基本的な問題があります (プロパティで 1 から数値へのすべてのサブリストを見つける必要があります|x[i] - x[i-1]| == m)。解決策があるかどうかを確認するにはどうすればよいですか? 私が見つけた潜在的な解決策を意味します。私はそれらを印刷するだけで、メモリに保存しません。解決策がない場合は、適切なメッセージを出力する必要があります。

私は、javascriptでのコードの出現の 9 日目の問題を解決しようとしています。

考えられるすべてのルートを取得するためにバックトラッキングを使用してから、それぞれのコストを計算しています。

私は PHP や C++ などの言語でバックトラッキングを行うことに慣れていますが、JS では行ったことがないので、Google のおかげで、PHP と C++ の両方で&パラメータのような可変パラメータを渡すことができないことがわかりました。

私の意図は、bestRoute変数を最適なルートに割り当てることです。これが問題の解決策だからです。

しかし、いくつかのサイトで return を使用してそうすると、次のような未定義の変数エラーが発生します。

これが私の現在のコードです。これは機能せず、最初に定義されたように bestRoute を出力します。

私はこの問題の声明で立ち往生しています。私のコードは機能しますが、使用itertools.permutationsしたため、非常に遅くなります。さらに、すべてまたは任意の入力に対して汎用にする方法がわかりません。バックトラッキングを使用する必要があると思いますが、ここでの使用方法は使用していません。

貴重な提案、アドバイス、またはコードは大歓迎です。はい、これは割り当てであり、コード全体を求めているわけではありません。ありがとう！

問題文は次のとおりです。

以下の異なる文字を異なる数字 (0、1、2、..、9) に置き換えて、対応する加算が正しく、MONEY の結果の値ができるだけ大きくなるようにします。値は何ですか？

SHOW + ME + THE = お金

方程式を満たす 3 つの解があります: 10376、10267、10265。したがって、正しい解は (最大の) 10376 です。同じ最大値に評価される複数のマッピングがある場合は、それらすべてを出力します。

課題:

この種の問題の正しい解決策を常に見つけることができるプログラムを Python で作成します。

これには少し問題があります。考えられるすべての組み合わせを生成したいと思います。数値は 1D 配列にあり、ファイルから読み取られます。今は問題がわかりません。モニターに出力されるすべての組み合わせが昇順であることはわかっています。一番小さい数字で終わると次の数字に上がらないのが難点。

例: 1,2,3,4,5、n = 5、p = 3 の 1D 配列ファイル。可能な組み合わせ:

1 2 3、1 2 4、1 2 5、1 3 4、1 3 5、1 4 5、2 3 4、2 3 5など...

これが私がこれまでに行ったことです：

学校のプロジェクトで、c# でプログラムを作成する必要があります。私は正しい軌道に乗っていると思いますが、この問題に固執しました。

プログラムのこのセクションでは、バックトラッキング アルゴリズムを作成する必要があります。私はクラス（英語、物理学、数学など）を持っており、すべてのクラスは特定の時間続きます。(たとえば、1h、2h、3h、5h など)。また、その日に学校で過ごすことができる時間を示す maxClassHours があります。アルゴリズムは、この maxClassHours を満たすクラスのすべての可能な組み合わせを可能な限り収集する必要があります。

特定のクラスに一度しか座れないことが重要です。そのため、数学の授業は 1 つしか受けられません。

たとえば、maxClassHours が 5 であるため、5 時間、別のクラスに座って過ごすことができます。

これらのクラスがあるとしましょう：

• 数学 - 2時間
• 物理学 - 1時間
• 音楽 - 2時間
• ダンス - 5h
• 体育 - 3時間
• 地理 - 5時間
• 英語 - 3時間
• フランス語 - 1時間
• サイエンス - 7h
• アート - 1時間

目標は、この 5 時間を満たすすべての可能な組み合わせを (バックトラック アルゴリズムを使用して) 見つけることです。

意味があるといいのですが...助けてくれてありがとう。

編集: バックトラッキング アルゴリズムをこの問題に適用する方法を理解したいと思います。

EDIT2: 何時間も作業を試みましたが、大きな進歩を遂げることができませんでした。そのため、助けを求めています...

問題

関数のどこかで、返すべきものを返していないことを認識しています。

再帰呼び出しを返していますが、「ずっと」返していないようです

環境

リスト内のすべての組み合わせの深さ優先検索を行っています。条件に合う組み合わせにたどり着いたら、戻りたい。

私は自分のコンビネーションの「状態」を維持しており、あるべき場所に戻っています (私はそう思います)。

私は何を間違っていますか？

コンボには、ステープル クラスのリストで構成される「ステープル」と呼ばれるプロパティがあります。最適な数を見つけるために、ディシジョン ツリーのステープルのリストを反復処理したいと考えています。

この場合、リスト内の各ステープル インスタンスの数量全体で最適な数が合計され、Combo インスタンスのプロパティとして保存/再計算されます。

この宿題は、小文字の az のみで作られた、指定された長さ n (無制限で不明!) のパスワードを解読するための再帰的な方法を作成することです。

ランダムなパスワードを作成するクラス「Password」は次のとおりです。

質問の詳細は次のとおりです。「コードを「クラック」する静的再帰メソッドを 作成する必要がありpublic static String findPassword(Password p, int length)ます。メイン メソッドの例を次に示します。

重要事項:

1. メソッドは、ANY ループを使用せずに、再帰的でなければなりません。
2. getPassword メソッドは使用できません。
3. String クラスのメソッドを使用する場合は、charAt、substring、equals、lengthのみを使用できます。
4. オーバーロードを使用することはできますが、他の方法を使用することはできません。(String.replace/String.replaceall は使用できません)
5. 静的 (グローバル) 変数は使用できません。
6. 配列は使用できません。"

これは私が今まで持っていたものですが、明らかにうまくいきません。:\

どうもありがとうございました！とても有難い！- トリプルS

再帰と DP を使用して、2 つの文字列の最長共通部分文字列を見つけようとしています。Longest Contiguous subsequence について言及しているわけではないことに注意してください。したがって、2 つの文字列が

再帰とバックトラッキングを使用してこれを実行しようとしています。ただし、問題は、以下のような再帰を使用すると、呼び出しスタックの上位にあるフレームに+1が前もって追加され、来る文字が実際に連続要素であるかどうかを認識しないことです。したがって、上記の例では、「bcdf」が答えになります。

今のところ、以下のコードは私が思いついたものです。不一致を見つけるたびに、カウントを 0 にリセットする方法に注意してください。また、 int countという変数を使用して一致する文字の数を追跡し、int maxcountという変数を使用して、プログラム内の任意の時点で最大のものを記録します。以下の私のコード。

これはうまくいきます。ただし、コードについて気に入らない点がいくつかあります

1. フレーム間で比較するためのグローバル変数 (static int maxcount) の使用
2. これは実際の動的プログラミングまたはバックトラッキングではないと思います。下位フレームは出力を上位フレームに返さず、それをどうするかを決定するからです。

グローバル変数を使用せずにバックトラッキングを使用してこれを達成する方法について、ご意見をお聞かせください。

PS：行列を維持したり、次のようなことをしたりするなど、問題に対する他のアプローチを認識しています

M[i][j] = M[i-1][j-1]+1 if(str[i] == str[j])

目的は問題を解決することではなく、洗練された再帰/バックトラッキング ソリューションを見つけることです。