問題タブ [subset-sum]

ソートされていないn整数のセットが与えられた場合、合計が 0 になるサイズ k (つまり、各セットに k 個の一意の要素がある) のすべてのサブセットを返します。

そこで、インタビュアーに次の解決策を提供しました (これはGeekViewpointで調べました)。余分なスペースは使用されず、すべてがその場で行われます。もちろん、コストはk=tuple、ソリューションのどこで O(n^k) の高い時間の複雑さです。

しかし、彼女は次の要件を課しました。

• 時間の複雑さを軽減するために、答えにハッシュマップを使用する必要があります
• 絶対に - 絶対に - 一般的なケースの時間の複雑さを提供する必要があります
• k=6、O(n^3)の場合のヒント

彼女は何よりも時間の複雑さに興味を持っていました。

新しい制約を満たす解決策を知っている人はいますか?

編集：

おそらく、正しい解決策では、マップは入力の要素を格納し、マップは の場合と同様にルックアップ テーブルとして使用されますk=2。

サブセットのサイズが 2 (つまりk=2) の場合、答えは自明です。ループして、すべての要素をマップにロードします。次に、今度は入力をループしてマップを検索しsum - input[i] where i is the index from 0 to n-1、それが答えになります。おそらく、この些細なケースは、何でもある場所に拡張できますk。

動的計画法を使用して、合計が正の整数 K に最も近いが等しくない配列内の正の整数のリストを見つけるにはどうすればよいでしょうか?

私はこれについて考えて少し立ち往生しています。

私は他のみんなと同じようにこの問題に苦しんでおり、この問題を説明するのに十分な数の投稿があると確信しています. ただし、それを完全に理解するという点では、サブセットサムの問題に関連して、ここにいるすべての偉大な人々から私の考えを共有し、より効率的な解決策を得たいと思いました.

インターネットで検索しましたが、実際には多くの情報源がありますが、完全に理解するために、アルゴリズムを再実装するか、独自のアルゴリズムを見つけたいと思っています.

私が苦労している重要なことは、セットのサイズが大きくなることを考慮した効率です。(制限はありません。概念的に大きいだけです)。私がアイデアを実装しようとしている 2 つのフェーズは、与えられた整数Tに等しい2 つの数値を見つけ、3 つの数値を見つけ、最終的にKの数値を見つけることです。私が持っているいくつかのアイデア;

2 つの整数部分については、基本的に配列O(nlogn)をソートし、配列内の各要素についてその負の値を検索しています。(つまり、配列要素が-3を検索する3の場合)。要素にインデックスを付けるO(1)を提供することで、ハッシュ テーブルを含める方がよいのではないでしょうか?

3 つ以上の整数については、すばらしいブログ投稿を見つけました。ただし、著者自身でさえ、多数には適用できないと述べています。

したがって、サブセットの問題にどのようなアイデアを適用できるかを2と3 およびそれ以上の整数にしました。大きな入力に対しても効率的な動的計画法を設定するのに苦労しています。

多目的/多目的サブセット和問題の高速な解決策を探しています。

追加の制約（IMOの計算を少し簡単にする）として、合計に含まれるすべての値が正であり、すべて既知の制限値にバインドされていると想定できます。

私は、1つの目的のサブセット和問題に対してO（NK）疑似多項式ソリューションがあることを知っています。私は、ウィキペディアとこのスタック交換の回答に基づいたソリューションを実装しました。

この問題を別の方法で説明すると、限界がわかっている正の数が2セットあります。最初のセットの値Aごとに、合計がAになる2番目のセットの値の組み合わせがあります。最初のセットのすべての値が、2番目のセットに関連付けられた対応する競合しない値の組み合わせを持っていることをアプリオリに知っています。 2番目のセットのどの要素が最初のセット値のそれぞれに関連付けられているかを計算するための既知の高速な方法はありますか？

負でない整数のリストが与えられた場合、リストNの数値の合計がX残りの と等しいかどうかをチェックするアルゴリズムを提案しますN-X。

言い換えれば、集合全体を含む部分和問題のより単純なケースです。

試みられた解決策

リストの要素を降順に並べ替えます。変数SUMを最初の要素に初期化します。最初の要素 (最大、 ) を削除しa(1)ます。現在のリストの要素を示すa(n)ようにします。n-th

リストには複数の要素がありますが、

1. またはのいずれか最も近いものに等しくSUMします。(最も近い平均が最小である場合)。SUM + a(1)SUM - a(1)a(2)|a(2) - SUM_POSSIBLE|

2. を削除しa(1)ます。

がまたはにSUM等しい場合、線形和が存在します。-a(1)a(1)

問題

上記のアルゴリズムを解決できないようです。正しい場合は、証明が必要です。それが間違っている場合 (より可能性が高い)、線形時間でこれを行う方法はありますか?

PS: 私が何か間違ったことをしているなら、許してください:S

マルチセットが別のマルチセットのサブセット和の和集合であるかどうかを検証するアルゴリズムを見つけたいのですが、一人で数時間苦労して失敗しました。

詳細は次のとおりです。

マルチセット A: 正の整数セット

マルチセット B: 正の整数セット (A 以下、理由は後でわかります)

アルゴリズム関数: B のすべての数値について、A の 1 つの数値または数値の合計が一致するかどうかを検証します。A の各数字は 1 回しか使用できず、A のすべての数字を使用する必要があります。B のすべての数値が一致する必要があります。

これを明確にする例: multiset A = {1, 3, 4, 4, 6} , B = {5, 6, 7} とします。

5 は 1 と 4 の合計、6 は 6、7 は 3 と 4 の合計であるため、アルゴリズムは「TRUE」を出力します。 B がチェックされます。

しかし、A = {2, 6, 8}、B = {7, 9} の場合、アルゴリズムは「FALSE」を出力しますが、2+6+8 = 7+9 ですが、B の数値は A の数値の合計ではありません。 .

いくつかのメモ:

1 既知の条件、A の数値の合計は B の数値の合計に等しい。

2 例が示すように、特定の数が複数回表示される場合があります。

3 マルチセットの各数値は 1 回しか使用できないため、1 つの解で 3 を使用すると (7 を取得するために)、別の解で再度使用することはできません。数字の 4 は 2 回現れるので、2 つのソリューションで使用できます。

4 1 つの数に対して複数の解が考えられます (7 は 1 と 6、または 3 と 4 のように) が、一部 (7 は 1 と 6 のように) は検証プロセスで間違っている可能性があります。

5 マルチセット A は大きくなく、最大で 30 要素です

私は最善を尽くしますが、私の解決策は常にマルチセット A と B のすべての条件をカバーすることはできません。これに対する解決策は明らかに私を超えていると思いました。

だから、私はあなたの賢い人々の助けが本当に必要です。私を助けてください。どんな答えでも大歓迎です！

（別のSO質問へのリンクを返信するか、これを重複して閉じる前に、質問を注意深く読んでください。これは、この問題の標準的なバリアントとは異なり、長い間検索してきたので、存在しないと確信しています。ここにこのような質問はありません）

X[i]のサブセットの合計である可能な最小のSが>=T（完全なセットの合計よりも小さいいくつかのターゲット値）であるかどうかを見つける必要があります。

セットはそれほど大きくはありませんが（約40要素）、指数関数的なバックトラッキングソリューションには大きすぎます。

数と合計が膨大であるため（約10 ^ 15）、動的計画法は機能しません（可能な状態の数が多いため、メモ化テーブルのメモリがすぐに不足します）。

同じ理由で、Pisingerによる線形時間アルゴリズムは機能しません（これはO（nr）であり、rは合計の上限であり、この場合は大きすぎます）。

合計が大きいが数が少ないこの場合に役立つ決定論的アルゴリズムはありますか？近似アルゴリズムに頼りたくありません。

この再帰がどのように機能するかを理解する必要があります。単純な再帰の例は理解できますが、より高度な例は難しいです。問題が発生したコードは2行だけだと思っていましたが、returnステートメント自体です。これがどのように機能するか、特に and/or 演算子については空白にします。どんな洞察も大歓迎です。

blockIndexメソッドを呼び出すときにの値を初期状態にリセットするにはどうすればよいですか?

それを呼び出して値 4 を渡すとします。その値が 9 より大きいかどうかを確認し、そうでない場合は at に要素を追加しpos(0)ます。しかし、関数をトレースすると、ベクトルのすべての値が追加されていることがわかります。1つの要素を追加したいだけで、それが9より大きいかどうかを確認し、そうでない場合は、初期値に戻します。どうすればいいですか？

重複の可能性：
サブセット和アルゴリズム

私は理解できない非常に簡単な問題を抱えています。セットの組み合わせを作成することで、可能な限り近づける必要のある数値と値の配列が与えられます。このアルゴリズムは再帰的に行う必要があります。結果は指定された数を超えることはできません。

たとえば、{6、9、4、2、7}の配列があり、14にできるだけ近づける必要がある場合、結果は13になります（要素9と4を選択することにより）。

これは私がこれまでに持っているものです：

2つのパラメーターを持つ再帰関数：追加しようとしている（または追加しない）要素に関する情報と、これまでの合計を提供するインデックス。すべての要素について、私はバイナリの決定を行います。それをsumSoFarに追加するかどうか。結果は私ができるだけ近づけなければならない数を超えることができないので、私は基本的なケースについて少し混乱しています。

誰かがこれで私を助けることができますか？

前もって感謝します！