問題タブ [subsequence]

正の数の配列が与えられ、n 以下の最小差を持つ 2 つの互いに素なサブ シーケンスを見つける必要があります。これらのサブシーケンスは、連続している場合と連続していない場合があります

これは DP を使用して実行できると思いますが、再発を導き出すことができません。

編集：反対票を投じた人々へ：コードが欲しくないこと、そしてすでに自分で試したことがあることは完全に明らかでした。私が探していたのは、サンプルの結果が得られた数学的プロセスの説明だけでした。

最初の質問。私は多くの調査を行い、最終的に尋ねることに頼ったので、どこかで答えを逃した場合はお詫び申し上げます. 私は本当に苦労している問題があります：

3 つのコマンド ライン引数を取る Python 3 スクリプトを作成します

。 1. 空白で区切られた n 個の文字列を含むテキスト ファイルの名前。
2. 正の整数 k。
3. 入力ファイルからの n 個の文字列から k 個の一意の文字列のすべての可能なサブシーケンス (1 行に 1 つのサブシーケンス) を格納するために、スクリプトが作成するテキスト ファイルの名前。

たとえば、コマンド ラインが gen.py input.txt 3 output.txt で、ファイル input.txt に次の行が含まれているとします。

Python Java C++ Java Java Python

次に、プログラムは次の行を含むファイル output.txt を作成する必要があります (

Python Java C++ Python
C++ Java
Java C++ Python
C++ Java Python

組み合わせは、ジェネレーター関数の実装 (つまり、yield キーワードを使用) で生成する必要があります。

私の理解では、サンプル出力に基づくと、これはサブシーケンスの定義に完全に従っていません。また、完全な順列でもないので、どうすればいいのか途方に暮れています。ファイル IO とコマンド ライン引数部分の実行方法は知っていますが、正しいサブシーケンスを取得できません。これを解決することになっているので、直接の回答は必要ありませんが、誰かが私に役立つ洞察を与えることができれば、それは大歓迎です.

問題: 整数配列 A[]、長さ = n、整数値 TARGET が与えられた場合。その合計が TARGET よりも小さく、その TARGET に最も近いことを満足するサブシーケンス (連続していない可能性があります) を見つけます。

例: A[] = [10, -2, 3, 7]. ターゲット = 14. 答え = {10, 3}

私は Hackerrank チャレンジでこの問題に遭遇しました。多項式時間の解を見つけることができませんでした。最初は、いくつかの動的計画法の問題に非常によく知られているように思えますが、この場合、「次よりも大きくない」および「最も近い」という条件が排除されているように見えます。その解決策。

動的計画法のアプローチに従う私の最初の考えから、i 問題 (i=0->n-1) で、A[i] を含むか含まないすべてのサブシーケンスを評価する必要があります。後者は A[i] を含みます。は S[i-1] として知られているため、最後の要素として A[i] を持つすべてのサブシーケンスに注目してください。

以前に解決した問題 (0->i-1) に頼ることができない場合、必要な合計がターゲットよりも小さく、ターゲットに最も近い必要があるため、小さなソリューションからは得られない可能性があり、2 番目の問題から生成される可能性があります。 、3 番目に最後の要素 A[i] を追加し、A[i] を含むすべてのサブシーケンスを反復するには、単一のセット {A[i]} を除いて、2^i - 1 個のサブセットすべてを通過する必要があります。

この種の問題に関する提案はありますか？

次の例のように、いくつかのシーケンスをマージしようとしています。

指定されたシーケンスはすべて、同じ重複のないシーケンス (指定されていません) のサブシーケンスです。'four'および例のように順序を決定できない場合は、'five'逆にすることもできますが、どちらの解決策でも問題ありません。

この問題は複数の配列アラインメントに似ていますが、より制限されている (重複がない、交差エッジがない) ため、(アルゴリズム的に) より簡単な解決策があると思います。例えば。すべての要素の結合から開始する場合、要素を並べ替えるだけで済みますが、入力シーケンスから基になる順序を推測する適切な方法を見つけることができないようです。

例はPythonであり、望ましい解決策もあるでしょうが、問題は一般的なアルゴリズムの性質です。

[255,7,0,0,255,7,0,0,255,7,0,0,255,7,0,0] この場合になるサブシーケンス内のすべての項目を含む最短の共通サブシーケンス (サブストリングではない) を見つけたいのですが 255,7,0,0、パターンの長さはわかりません。

このシーケンスのように途中で意味不明な部分があっても、プログラムは動作するはずです。255,7,0,0,4,3,255,5,6,7,0,0,255,7,0,0,255,7,0,1,2,0、それは繰り返されるサブシーケンスを返す必要があります255,7,0,0。

最長共通サブシーケンスを試しましたが、アルゴリズムが貪欲であるため、このケースでは機能しません。最短一致ではなくすべての一致が返されるためです。あなたの助けは非常に高く評価されています。

大学の課題で行き詰まっています。タスクは、再帰的で動的なプログラミング方法を見つけて、配列の最も長く、結果として昇順のサブシーケンスの長さを計算することです。たとえば、配列が {4 , -5 , -3, -2, 5, -2, 0, 3 , 2} の場合、最大長はサブシーケンス {-5, -3, -2, 5 を持つ 4 になります。 }。再帰的な方法を見つけるのに苦労しています。再帰的な方法がなければ、動的な方法を見つけることは不可能です。
私は何かをプログラミングしようとしましたが、それが間違っていることを知っており、修正方法がわかりません: