問題タブ [subset-sum]

この疑似コードからJavaでサブセットの合計問題を実装する方法を知っている人はいますか?

これは本当に私を困惑させているので、コメントを追加できれば素晴らしいでしょう!!!

2n のすべての合成を n 個の負でない整数変数の合計として導出するエレガントな方法があるかどうか疑問に思います。

たとえば、n = 2 変数 x と y の場合、2 つの部分を持つ 5 つの合成があります。

x = 0 y = 4; x = 1 y = 3; x = 2 y = 2; x = 3 y = 1; x = 4 y = 0

x + y = 4 = 2n となります。

より一般的には、問題は、合計が s に等しい n 個の非負の整数変数への s のすべての構成を見つけるように定式化できます。

この問題を効率的に計算する方法についての提案は歓迎され、いくつかの擬似コードは大歓迎です。ありがとう。

編集: Perl と Prolog のように解決策を以下に示しますが、再帰呼び出し中に配列などの線形データ構造を渡したり操作したりする必要があるため、 Java実装では新しい問題が発生する可能性があり、そのような方法は n が取得されるにつれて非常に高価になる可能性があります。もっと大きいので、この問題に対する代替の (そしてより効率的な) Java実装があるのではないかと思います。

Given a set A containing n positive integers, how can I find the smallest integer >= 0 that can be obtained using all the elements in the set. Each element can be can be either added or subtracted to the total. Few examples to make this clear.

A = [ 2, 1, 3]

Result = 0 (2 + 1 - 3)

A = [1, 2, 0]

Result = 1 (-1 + 2 + 0)

A = [1, 2, 1, 7, 6]

Result = 1 (1 + 2 - 1 - 7 + 6)

サブセットにない数の合計になる整数のセットのサブセットを見つけることが可能かどうかを尋ねるサブセット問題のバージョンがあります。誰もがアルゴリズムが何であるか知っていますか？ありがとう

これは、配列を並べ替えて、必要な条件が満たされるまで大きな数値を取得することで実行できることを私は知っています。それには少なくともnlog（n）のソート時間がかかります。

に改善はありますかnlog(n)？

すべての数値が正であると想定できます。

最近、スーパーセットからゼロサム部分集合を見つける部分和問題に興味を持ちました。SOでいくつかのソリューションを見つけました。さらに、動的プログラミングアプローチを使用する特定のソリューションに出くわしました。彼の定性的な説明に基づいて、彼のソリューションをPythonで翻訳しました。これを最適化して、メモリを大量に消費する大きなリストにしようとしています。この特定の問題を解決するための最適化やその他の手法を誰かが推奨できますか? Pythonでの私の試みは次のとおりです。

遺伝的アルゴリズムを使用して部分和問題を解決するプロジェクトを行う必要があります。残念ながら、アルゴリズムをコーディングしているときに大きな問題が見つかりました...

私のアルゴリズム:

• 解決策が見つからず、ステップ数がステップ数よりも少ない限り:
• 各染色体の確率と分布関数を計算する
• 選択を行う（ルーレット）
• 交差させるn個の染色体を選択する
• 交差点を実行します（交差点はランダムに選択されます）
• 突然変異させるm染色体を選択する
• 突然変異を行う
• 解決策を見つけた場合は停止します

(アルゴリズムは本「遺伝的アルゴリズム + データ構造 = 進化プログラム、第 2 章」から引用) （ステップ内の）交差点の数は、プログラムオプションで厳密に設定されています。

問題は、集団内で特定の (比較的少ない) 数のステップの後、すべての染色体が同一になることです。問題はこのグラフを示しています: http://imageshack.us/m/96/7693/wykresb.png

私が間違っていることは何ですか？修正方法は？前もって感謝します。

編集：

ここで、私のアプリからのログを見つけることができます: http://paste.pocoo.org/show/391318/

ルーレットは最善の解決策ではないと思います (deong が言ったように)。突然変異も改善する必要があります。

整数のセットが与えられた場合、合計すると特定の値になるサブセットを見つける方法...サブセットの問題?

例 : S = {1,2,4,3,2,5} および n= 7 合計が n である可能なサブセットを見つけます。私はグーグルで多くのリンクを見つけようとしましたが、明確ではありませんでした。Javaでこれをどのように解決できますか?使用するデータ構造とその複雑さは何ですか?

Greplin チャレンジのレベル 3 で苦労しています。なじみのない人のために、ここに問題があります：

最大数が残りの数の合計である配列のすべてのサブセットを見つける必要があります。たとえば、次の入力の場合:

(1、2、3、4、6)

サブセットは

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

コードを実行する必要がある番号のリストを次に示します。パスワードはサブセットの数です。上記の場合、答えは 4 になります。

3、4、9、14、15、19、28、37、47、50、54、56、59、61、70、73、78、81、92、95、97、99

400 万以上の 22 の数字の組み合わせをすべて構築し、それらすべてをテストして正しい答えを得るソリューションをコーディングすることができました。問題は、クランチするのに40分以上かかることです. Web を検索すると、これに対する答えを 1 秒もかからずに得るアルゴリズムを作成できた人が何人かいるようです。計算コストの高い総当たり法よりも、これに取り組むためのより良い方法を疑似コードで説明できる人はいますか? それは私を夢中にさせています！

他のセット B のサブセットの合計と等しいセット A のサブセットの合計を見つける必要がある現実世界の問題 (宿題ではありません!) があります。

非常によく似た質問と役立つ回答がここにあります。

次の例を検討してください。

その質問に対する受け入れられた回答で提供されたコードを使用すると、次の出力が得られます。

私の目的のために、入力セットの最も少ない要素を使用する回答のみが必要です。この例では、私はただ欲しい

他のすべての回答にも合計があるため200です4000。つまり、「最も単純な」可能な合計を探しています (使用する要素が最も少ないという意味で)。誰かがこれを行うための合理的に効率的な方法を提案できますか? （私の配列はそれほど大きくないので、力ずくで大丈夫です。）

また、出力の 2 行目はsum(200 4000 4000) ...正しくないことに注意してください。残念ながら、なぜこれが起こっているのかを理解するのに十分なほどアルゴリズムを理解していません。4000@a

これらのいずれかで何か助けていただければ幸いです。