問題タブ [subset-sum]

NP完全なパーティション問題のバリエーションである問題があります。これは最適化の問題であり、決定の問題ではありません。

問題: 和の差が最小になるように数のリストを 2 つの部分集合に分割し、2 つの部分集合を見つけます。偶数の場合n、サイズは でn/2、奇数の場合はfloor[n/2]とceil[n/2]です。

疑似多項式時間 DP アルゴリズムが正確な解に最適であると仮定すると、これを解決するためにどのように変更できますか? そして、これを解決するための最良の近似アルゴリズムは何でしょうか?

N 個の正の整数のコレクションがあり、それぞれが (比較的小さい) 定数 C で区切られています。値 K より大きい (または等しい) 最小の合計を持つこれらの数値のサブセットを見つけたいと考えています。

関連する数値はそれほど大きくありません (<100) が、最悪の場合でも優れたパフォーマンスが必要です。私は、Pisinger の動的プログラミング アルゴリズムをこのタスクに適用できるのではないかと考えました。それは O(NC) 時間で実行され、有界の正の数の要件をたまたま満たしています。

[編集]:番号はソートされておらず、重複している可能性があります。

ただし、これを自分で行うにはアルゴリズムを十分に理解していません。実際、それが基づいている仮定が今でも成り立つかどうかさえ定かではありません...

-このアルゴリズムを私のニーズに合わせることは可能ですか?

-または、同様に効率的な、使用できる別の線形アルゴリズムはありますか?

-誰でも疑似コードまたは詳細な説明を提供できますか?

ありがとう。

私が調査していた Subset-Sum コードへのリンク: Pisinger によるサブセット合計アルゴリズムへの高速ソリューション

（これが不適切な表現/フォーマット/その他である場合はお詫び申し上げます。私はまだStackOverflowに慣れていません...）

私は動的プログラミングの問題を解決しようとしていますが、問題の一部には、合計すると数値「n」になる一連の「p」数値の順列の数を見つけることが含まれます。p 個の数値のセット内の各数値は、0 から n までの範囲である必要があります。

たとえば、n = 4 で p = 3 の場合、次の 12 の順列があります。

私はこのDPアプローチから始めました。

私の基本ケースは

(たとえば、p=3 桁の n(4,0) は 3 であり、{4,0,0},{0,4,0},0,0,4}

再帰的なケース

(例: n(1,2) = n(1,1) * n(0,2) n(1,0) * n(0,1) * 2 に再帰)

上記のアプローチでは正しい答えが得られないため、正しい方向に進んでいるかどうかはわかりません。私を正しい方向に導いてください。

サブセット問題はウィキペディアで次のように定義されています。

整数の集合が与えられたとき、合計がゼロである空でないサブセットはありますか? たとえば、セット { −7, −3, −2, 5, 8} が与えられた場合、サブセット { −3, −2, 5} の合計はゼロになるため、答えはイエスです。

また

整数の集合と整数 s が与えられたとき、合計が s になる空でないサブセットはありますか?

この問題のブルート フォース ソリューションは指数関数的です (N 個の数のすべてのサブセットを循環し、それらのすべてについて、サブセットの合計が正しい数になるかどうかを確認します)。指数時間で実行されるブルート フォース用に最適化されたバージョンもあります。

2 次と多項式の時間計算量の間で総当たり解 (上記の質問に対する正確な解) を計算できるアルゴリズムがあるとします。

P=NP の問題、時間の複雑さなどに関連してどのように考えられるでしょうか?

アルゴリズムが存在すると仮定すると、サブセット合計問題の最先端の改善になるでしょうか?

（私はこの分野の専門家ではないので、何かが意味をなさない、または明確でない場合は、できる範囲でこの質問に追加の情報を提供します:)）

指定: 整数値の配列 K,M

質問: 与えられた配列のすべての K 個の要素サブセットから、合計が値 M 未満になるように取得できる最大合計を見つけますか?

この問題に利用できる非動的プログラミング ソリューションはありますか? または、dp[i][j][k] のみの場合は、このタイプの問題しか解決できません! アルゴリズムを教えてください。

{a1、a2、...、an}などの正の整数の配列があり、次の条件を満たす配列のすべての可能なサブセットを見つけたい:

ここで、K は正の整数です。この問題の解決策が動的プログラミングであることは知っていますが、この場合の使用方法を考えることができません。助けてください。

PS：すべてのサブセットが正確に必要なわけではありませんが、形成されたすべてのサブセットのすべての要素の積と言えます。

アプリケーションで必要な次の数学の問題があり、近似ではなく最適な解を見つける効率的な方法があるかどうか疑問に思っています。

1. 正と負の値のリストがあります。
2. これらの値の合計は範囲 (x, y) 内にあります。
3. 残りの値の合計が範囲内に収まるように、除外できる値の最大数を知りたいです。

例：

15 を削除すると、SUM = 0 になり、範囲外になります。5 つの値が削除されました。

一方、15 を削除することから始めて、次に -10、-5、-2 を削除すると、4 つの値しか削除できません。

考えられるすべての組み合わせを単純に試すアルゴリズムを書いたことがありますが、値が 25 以上になると、そのパフォーマンスは急速に低下します。100 ～ 200 の値の場合、10 分の 1 秒で結果が必要です。

現在、絶対値に基づいて小さい値から大きい値に値を並べ替え、合計が範囲内になくなるまで値を 1 つずつ削除します。明らかに、常に最適なソリューションが得られるとは限りません。

これがこの種の質問に適切な場所ではなく、別のフォーラムを参照できる場合は、それも役に立ちます。

より多くの反応を引き出すために、MathExchange に相互投稿しま​​した。

================================================== ==============================

元の質問を StackOverflow で書いていたときに、以前に質問されたことに気付きました。

部分和問題と呼ばれるものがあることが判明したので、ウィキペディアに行ってこの部分を見つけました。

しかし、ウィキペディアに書かれた疑似コードを理解するのに問題があります。

たとえば、目的は S に一致する最も近い数のセットを見つけることだと思いました。

しかし、ここで S はリストです。この要素が 0 の S リストは何ですか?

そして、一体何 if y + cs/N < z ≤ sですか？これをコードに書き出すにはどうすればよいですか？

誰かがこれをphpコードに翻訳するのを手伝ってくれることを望んでいました.

少なくとも私はそのことに精通しています。完全な翻訳である必要はありません。

答えがこのおおよそのアルゴリズムを理解して、自分でphpコードで書くのに十分である限り、それで十分です。