問題タブ [subset-sum]

合計が30になる5つの1桁の繰り返しのない数字のすべてのセットを検索したいとします...[9,8,7,5,1]、[9,8,7]になります、4,2]、[9,8,6,4,3]、[9,8,6,5,2]、[9,7,6,5,3]、および[8,7,6、 5,4]。これらの各セットには、5つの繰り返しのない数字が含まれ、合計で30になります。

どんな助けでも大歓迎です。私が使用するための単なる出発点でさえ素晴らしいでしょう。

私は1つの方法を思いつきました。これは、長い道のりのようです。すべての一意の5桁の数字（12345、12346、12347など）を取得し、数字を合計して、指定された合計と等しいかどうかを確認します（例：30）。含まれている場合は、一致する可能性のあるセットのリストに追加します。

私は個人的なプロジェクトのためにこれを行っています。これは、実際にすべてを一度に解決することなく、カックロのパズルを解くのに役立ちます。ええ、それは浮気かもしれませんが、それは...それはそれほど悪くはありません...：P

はい、これは宿題/実験課題です。「バックトラッキング」を使用してサブセット和の問題を解決するためのアルゴリズムを考え出す/見つけることに興味があります (理解できます:P)。

誰でも役に立つリソースを持っていますか? 私は最後の 1 時間かそこらをグーグルで過ごしましたが、実際に使用できると思われるものを見つけることにあまり似ていませんでした。xD

ありがとうございます！

部分和問題を解くための新しいアルゴリズムを思いついたのですが、それは多項式時間だと思います。私が間違っているか、天才だと言ってください。

クイックスターターファクト：

部分和問題はNP完全問題です。多項式時間でそれを解くことは、P=NPを意味します。
長さNのセット内のサブセットの数は2^Nです。

より有用な一方で、長さNの一意のサブセットの数は、最大でセット全体の合計から最小の要素を引いたものです。または、サブセットが生成できる可能性のある合計の範囲は、すべての負の要素の合計の間にあります。そして、すべての正の要素の合計。これは、すべての正または負の合計よりも大きいまたは小さい合計はあり得ないためです。これらの合計は、要素を追加すると線形速度で増加します。

これが意味するのは、Nが増加すると、重複するサブセットの数が指数関数的に増加し、一意で有用なサブセットの数が直線的にのみ増加することです。可能な限り早い機会に重複サブセットを削除できるアルゴリズムを考案できれば、多項式時間で実行できます。簡単な例は、バイナリから簡単に取得できます。2の累乗である数値のみから、任意の整数値に対して一意のサブセットを作成できます。そのため、他の数を含むサブセット（2の累乗がすべてある場合）は重複していて無駄です。それらとその導関数を計算しないことにより、2の累乗である数値が任意の整数と比較して対数的に発生するため、アルゴリズムの実行時間を実質的にすべて節約できます。

そのため、これらの重複を削除し、それらとそのすべての導関数を計算する必要をなくす単純なアルゴリズムを提案します。

まず、O（N log N）のみのセットを並べ替え、正と負の2つに分割します。負の数の手順は同じなので、正の数の概要のみを説明します（明確にするために、セットは正の半分だけを意味します）。

sumでインデックス付けされた配列を想像してみてください。この配列には、正の側のすべての可能な結果の合計のエントリがあります（線形のみです。覚えておいてください）。エントリを追加すると、値はサブセット内のエントリになります。したがって、array [3] = {1、2}のようになります。

一般に、セット内のすべてのサブセットを列挙するように移動します。これを行うには、1つの長さのサブセットから始めて、それらに追加します。すべての一意のサブセットがある場合、それらは配列を形成し、Horowitz/Sahniで使用されている方法でそれらを単純に反復します。

ここで、「第1世代」の値から始めます。つまり、元のデータセットに重複する数値がなかった場合、これらの値に重複がないことが保証されます。つまり、すべての単一値サブセット、およびセットのすべての長さから1つの長さのサブセットを引いたものです。これらは、セットを合計し、各要素を順番に減算することで簡単に生成できます。さらに、セット自体は、有効な第1世代の合計とサブセット、およびサブセットの個々の要素です。

次に、第2世代の値を実行します。配列内の各値をループし、一意のサブセットごとに、値がない場合はそれを追加して、新しい一意のサブセットを計算します。重複していると、楽しいことが起こります。衝突リストに追加します。新しいサブセットを追加するときは、それらが衝突リストにあるかどうかを確認します。あまり望ましくない（通常は大きいが、任意である可能性がある）等しいサブセットによってキーを設定します。サブセットに追加する場合、衝突が発生したとしても、何もしません。より望ましいサブセットを追加する場合、チェックを見逃して追加し、共通のサブセットを生成します。その後、他の世代のために繰り返します。

この方法で重複サブセットを削除することにより、重複をセットの残りの部分と結合し続ける必要も、衝突をチェックし続ける必要も、合計する必要もありません。最も重要なことは、一意ではない新しいサブセットを作成しないことで、それらから新しいサブセットを生成しないことです。これにより、アルゴリズムがNPからPに変わる可能性があります。これは、サブセットの成長が指数関数的ではなくなったためです。破棄します。それらの大部分は、次世代で「複製」し、他の重複しないサブセットと組み合わせることによって、より多くのサブセットを作成する前に行われます。

私はこれをあまりよく説明していないと思います。私は写真を持っています...それらは私の頭の中にあります。重要なことは、重複するサブセットを破棄することで、実質的にすべての複雑さを取り除くことができるということです。

たとえば、（この例を手作業で行っているため）ゼロを目指す-7から7（ゼロではない）の単純なデータセットを想像してみてください。並べ替えて分割すると、（1、2、3、4、5、6、7）が残ります。合計は28です。ただし、2 ^ 7は128です。したがって、128個のサブセットが1 .. 28の範囲に収まります。つまり、100セットが重複していることが事前にわかっています。8の場合、スロットは36しかありませんが、サブセットは256になります。したがって、重複の数が以前の2倍を超える220になっていることが簡単にわかります。

この場合、第1世代の値は1、2、3、4、5、6、7、28、27、26、25、24、23、22、21であり、それらを構成コンポーネントにマップします。

ここで、新しいサブセットを生成するために、各サブセットを順番に取得し、相互サブセットがない限り、他のサブセットに追加します。たとえば、28と27にはhueg相互サブセットがあります。したがって、1を取得して2に追加すると、3 = {1、2}になりますが、お待ちください。すでにアレイに含まれています。これが意味するのは、すでに2が含まれているサブセットに1を追加しないこと、およびその逆のことです。これは、3のサブセットと重複しているためです。

今、私たちは持っています

ここで、すべてに2を追加します。

3？

ご覧のとおり、毎回新しいサブセットを追加していますが、量は直線的にしか増加していません。

4？

5？

これで範囲内のすべての値が得られたので、停止してリスト1-28に追加します。負の数について繰り返し、リストを繰り返します。

編集：

このアルゴリズムは、どのような場合でも完全に間違っています。合計が重複しているサブセットは、到達方法が異なるため、つまり、折りたたむことができないため、サブセットを生成できる目的で重複することはありません。

等しい k サブセットアルゴリズムの優れた効率的なアルゴリズムを知っている人はいますか? できれば、100要素のベクトルを処理できるcまたはc ++で、複雑さと時間の見積もりが必要になる可能性があります

元。9 要素ベクトル

x = {2,4,5,6,8,9,11,13,14}

i は合計 = 24 ですべての k=3 の互いに素なサブセットを生成する必要があります。アルゴリズムは、要素の合計が 24 である k 個の互いに素なサブセットがあるかどうかをチェックし、それらを昇順 (サブセット内およびサブセット間) でリストするか、または解が存在しません

ソリューション

解 1: {2 8 14} {4 9 11} {5 6 13}

解 2: {2 9 13} {4 6 14} {5 8 11}

ありがとう

最初に言っておきますが、私は理論などについてよく知りません。しかし、これが NP なのか NP 完全な問題なのか疑問に思っていました。具体的には、部分和問題の特殊なケースのように聞こえます。

とにかく、私が最近プレイしている Alchemy というゲームが、この考えを促しました。基本的には、4 つの基本要素から始めて、それらを組み合わせて他の要素を作成します。

たとえば、要素を作成する場合、これは短い「レシピ」です。

では、コンピュータが 4 つの基本的な要素しか作成できなかったとしますが、要素の複数のセットを作成できます。したがって、他の要素を組み合わせて任意の要素を作成するプログラムを作成します。このプログラムは、電球を作成するリストをどのように処理しますか?

明らかに、火+空気=エネルギー、土+土=砂、砂+火=ガラス、エネルギー+ガラス=電球です。

しかし、リストを処理するプログラムを作成し、ブルートフォース型のメソッドを実行してすべての要素を調べ、そのレシピを確認することなくそれを理解する方法は考えられません。

これはNPの問題ですか？それとも、これを理解できないだけですか？

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

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

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

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

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

配列 int [] arr={1,2,4,5,7} があり、数字も 6 であると仮定すると、結果を 01100 にする必要があります。つまり、配列内で 2+4=6 になるため、結果は合計の数値が 0 の場合は 1 になり、それ以外の場合は、結果のビット数が配列の長さと同じ数になる必要があります

この操作を実行する Java メソッドが必要です

How would you go about testing all possible combinations of additions from a given set N of numbers so they add up to a given final number?

A brief example:

• Set of numbers to add: N = {1,5,22,15,0,...}
• Desired result: 12345

整数の行列の最大2次元サブセットを計算するアルゴリズムを作成するタスクが与えられました。-しかし、私はそのようなアルゴリズムのヘルプには興味がありませんが、これを解決できる可能性のある最良の最悪の場合の複雑さを知ることにもっと興味があります。

現在のアルゴリズムはO（n ^ 3）のようなものです。

私は、マトリックス内の要素を単純に合計することによって、マトリックスをいくつかのサブマトリックスに分割することによって、分割統治法のようなものを検討してきました。そしてそれにより、近似解を見つけるために考慮しなければならない行列の数を制限します。

サブセット合計の問題を解決するのに役立つ 2 つの関数を作成しました。私はエラーが発生しているようです。に 2 つの引数を渡していることがわかりますlist-sum。私はこのプログラムを数時間いじっています。誰かが問題を見つけることができるかどうか疑問に思っていました。

これは私のlist-sumです：

これは、使用する私の関数ですlist-sum:

1 つの引数で「compound-procedure #(number) ssum」を呼び出したこと、および 2 つの引数が必要であることを示しています。として渡してい(ssum 8 (list 1 3 5 7))ます。

私の質問は次のとおりです。

1. 機能を正しくセットアップしましたか?
2. my 内のリストの数値を合計する簡単な方法はありssumますか?
3. 私はSchemeも初めてです。コードを短縮する明らかな方法を見つけた場合は、お気軽に修正してください。