問題タブ [subset-sum]

このような数値の配列がいくつかあります（配列の各要素は0または1の値のみを取ることができます）

配列を合計したときに、結果の配列に 2 の倍数である個々の要素が含まれるようなサブセットを見つけたいと考えています。結果の配列は、2 の倍数である任意の値を持つことができます。

もう一つの例：

この例では、v1+v2+v5 と v3+v6+v7 が適切な回答です。

力ずくの解決策を念頭に置いていますが、より効率的な方法があるかどうかを確認したかったのです。これは部分和問題と同じですか?

私は答えを求められたこの質問に汗を流してきました（技術的には宿題です）。私はハッシュテーブルを検討しましたが、これをどのように機能させるかについての正確な詳細に固執しています

ここに質問があります：

整数のkセット_A1、A ₂、..、合計サイズO（n ）のA k_が与えられた場合 、₁ ϵ A ₁、a ₂ ϵ A ₂、.. 、_ak ϵ A _k、a ₁ + a ₂ + .. + a _{k −1} = _akとなるように。アルゴリズムはTk （n）時間で実行する必要があります。ここで、_{T k}（n）= O（n ^{k /2} ×logn ）（偶数kの場合） 、O（n ^{（k +1）/ 2 ）（} kの奇数値の場合）。

私がこれを解決することに近づくことができるように、誰かが私に一般的な方向性を与えることができますか？

アナグラム：

アナグラムは一種の言葉遊びであり、元の文字をすべて 1 回だけ使用して、単語またはフレーズの文字を並べ替えて新しい単語またはフレーズを作成した結果です。

部分和問題:

問題は次のとおりです。整数のセットが与えられた場合、合計がゼロである空でないサブセットはありますか?

たとえば、セット { −7, −3, −2, 5, 8} が与えられた場合、サブセット { −3, −2, 5} の合計はゼロになるため、答えはイエスです。問題は NP 完全です。

n 個の単語からなる辞書があるとします。ここで、アナグラム生成の問題は、入力のすべての文字を使い果たす辞書 (n 個の単語) 内の単語のセットを見つけることとして述べることができます。部分和問題のようなものになりませんか。

私が間違っている？

喜んでお手伝いさせていただきます。

次の問題があります。

数値のリストseqと目標数値が与えられ、次の 2 つのことを記述する必要があります。

1. Trueサブシーケンスの合計がターゲット数と等しいか、そうでない場合に返される再帰的なソリューションFalse。例：

   /li>

2. 次に、前のソリューションで書いたものを使用してソリューションを作成する必要がありますが、キーがタプルである辞書を使用するメモ化を使用します。 (len(seq),target)

番号1については、これまでに得たものです：

私はそれが正しいかどうかわからないので、何らかの意見を得ることができれば感謝します.

番号 2 の場合:

メモ化して正解を出すことができないので、ここでいくつかのガイダンスをいただければ幸いです。

喜んで手伝ってくれてありがとう！

わかりました、私が開発しているカードゲームは、誰かがそれを知っていれば、スコパにかなり似ています. デッキには 40 枚のカードが含まれており、それぞれ 10 枚のカードの 4 つの異なるスートに分割されています (エース => 値 1、2 => 値 2、3 = ...、4、5、6、7、ナイフ、クイーン、キング => 値 10)。 ）。2 人のプレイヤー (実際には AI と人間のプレイヤー) がいて、手札に 4 枚のカードがあります。

テーブルには 4 枚のフリー カードがあり、プレイヤーは次のルールに従ってのみそれらを受け取ることができます。テーブルからクイーンを取る）。2) 数字カード (エースから 7) は、同じ数字のカードまたはそれより小さい数字のカードを合計で取ることができます (たとえば、7 を持っている場合、7 または {エース、6} または {3、4) を取ることができます。 } または { エース、スリー ツー })。

AI がターン中に最終的に取ることができるカードを見つける時が来ました。

このアルゴリズムを何らかの方法で改善できると思いますか? このコードをできる限り短くして、デバッグと保守を容易にしようとしています...また、誰かが重複した組み合わせを避けるためのよりエレガントなソリューションを持っている場合は、本当に感謝します(私は{ ハートのエース、スペードの 2 つ } と { スペードの 2 つ、ハートのエース } の両方を取得したくありません... そのうちの 1 つだけです)。

よろしくお願いします！

これが NP 困難な問題であることは承知していますが、多くのユーザーがこの機能を要求してきました (基本的に、現在の注文のアイテムのセットは、私たちが実行している取引の 1 つに適格ですか? または、現在のご注文の商品と他の 1 つの商品が対象となりますか?)

機能を提供することは、正しい答えを見つけることよりもユーザーの利便性に関するものであるため、X 個以上の項目がある場合はアルゴリズムを実行しないなど、時間をかけずにこれを行うためのショートカットを検討してきました。ラグ、またはアルゴリズムを介して最近追加された X アイテムのみを実行します。

アドバイスを提供できる前に、同様の問題に対処した人はいますか?

与えられたリストのすべてのサブリストを整数で出力したいこの関数を書いています。これらの整数の合計は、指定された数に等しくなければなりませんn。i値0で始まるヘルプ変数もあります。リストと各サブリストはどちらもArrayListです。したがって、メソッドは現在次のようになります。

もちろん、私はすでにメソッドを持っていますsum()。メソッドはこれを実行します。とするnumbers = [1, 3 , 4]とn == 4、メソッドは[4]and[1 ,3]を出力する必要がありますが、出力するのは[1, 3]？forループはそのトリックを正しく実行する必要があると思いますか？誰かが私を正しい軌道に乗せてくれれば幸いです。

更新：メソッドに与える値：

更新2：

再帰的にしたいと言うのを忘れました:)

サブセット和問題を解く次の方法を検討してください。

私はここからそれを持っています：

http://news.ycombinator.com/item?id=2267392

それを「より効率的に」することが可能であるというコメントもあります。

どのように？

また、少なくとも上記の問題と同じくらい速い問題を解決する他の方法はありますか？

編集

スピードアップにつながるアイデアに興味があります。私が見つけた：

https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2

これは線形時間アルゴリズムに言及しています。しかし、私は紙を持っていません、おそらくあなた、親愛なる人々、それがどのように機能するか知っていますか？おそらく実装？おそらく完全に異なるアプローチ？

編集2

現在、フォローアップがあります：
Pisingerによるサブセット和アルゴリズムの高速ソリューション

これらの質問に続いて、サブセット和問題 と固定サブセットサイズのサムサブセットは、正確にk個の整数、k<=nを使用することを余儀なくされるサブセット和問題を解くための一般的なアルゴリズムは何か疑問に思いました。

Evgeny Kluevは、k = 4に最適を使用し、その後、k-4にブルートフォースアプローチを使用し、残りに最適を使用すると述べました。ここでブルートフォースアプローチと最適なk=4アルゴを組み合わせることで、彼が何を意味するのかを誰もが理解できますか？

おそらく誰かがより良い、一般的な解決策を知っていますか？

これは私の前の質問へのフォローアップです。私はまだそれが非常に興味深い問題だと思っています.1つのアルゴリズムがもっと注目に値するので、ここに投稿しています.

ウィキペディアから:各 xi が正で、同じ定数で囲まれている場合、Pisinger は線形時間アルゴリズムを見つけました。

同じアルゴリズムを説明しているように見える別の論文がありますが、私には読むのが少し難しいのでお願いします.4ページの疑似コード（balsub）を実用的な実装に変換する方法を知っている人はいますか？

これまでに収集したいくつかのポインターを次に示します。

http://www.diku.dk/~pisinger/95-6.ps (論文)
https://stackoverflow.com/a/9952759/1037407
http://www.diku.dk/hjemmesider/ansatte/pisinger /codes.html

PS: 私はこのアルゴリズムを正確に主張しているわけではないので、他の同様のパフォーマンスのアルゴリズムを知っている場合は、遠慮なく以下に提案してください。

編集

これは、oldboy によって次のように投稿されたコードの Python バージョンです。