整数Aと整数N、Mの配列が与えられています。ここで、(sum(S)mod M = N)whereのすべてのサブセットSを探したいと思います。 Aは同じ値の複数の整数を持つことができます。 私の場合、Nは0の範囲になります< = n < = 31、Mは32、Aはnと同じ範囲の整数を含みます。モジュロでサブセット和バリアント
これを行うには良い/「速い」方法がありますか?
ありがとうございます!
整数Aと整数N、Mの配列が与えられています。ここで、(sum(S)mod M = N)whereのすべてのサブセットSを探したいと思います。 Aは同じ値の複数の整数を持つことができます。 私の場合、Nは0の範囲になります< = n < = 31、Mは32、Aはnと同じ範囲の整数を含みます。モジュロでサブセット和バリアント
これを行うには良い/「速い」方法がありますか?
ありがとうございます!
それはO(2 N/2ログ(2 N/2))= O(2 N/2(N/2))、あなたの制約を持つこの作品で解けるですC++上では1秒未満です。
必要なのは、次のとおりです。
1)配列の最初のn/2
要素のすべての可能な合計を計算し、合計は、アレイ
2の左部分に表示される場所left[sum] =
回数map<int, int> left
に入れ)配列の最後のn/2
要素のすべての可能な合計を計算し、各サムのためにS
チェックがマップleft
は、あなたがbitmasを使用する可能性のあるすべての合計を見つけるために(N - S + M)%M
が値を含んでいませんks:
for (int mask = 1; mask < pow(2, n/2); mask++) {
int sum = 0;
for (int i = 0; i < n/2; i++)
if ((int) (mask & (1<<i)))
sum += A[i];
}
あなたが数えたければ、動的プログラミングでO(|A| * M)
で解決できます。ここでは例です:
A = [2, 6, 4, 3]
M = 5
0 1 2 3 4
S = 0 0 0 0 0 // The number of subsets with sum i (mod M)
// Iterate over A (through S each time)
2 0 0 1 0 0
6 0 1 1 1 0
4 1 2 2 1 1
3 3 3 3 3 3
Pythonコード:
A = [2, 6, 4, 3]
M = 5
S = [0 for i in xrange(0, M)]
STemp = [0 for i in xrange(0, M)]
for a in A:
for (i, v) in enumerate(S):
ii = (a + i) % M
STemp[ii] = S[ii] + v
STemp[a % M] = STemp[a % M] + 1
S = STemp
STemp = [0 for i in xrange(0,M)]
print S # [3, 3, 3, 3, 3]
ねえ!私は実際に目標合計(N)がどこから来ているのか分かりません。また、あなたが作ったテーブルを説明することができます、それが何を言っているのか、あなたが読むことができるものを実際には得られません。ありがとう! –
@AntonAndellご利用いただきありがとうございます。これは、「i」が「0」から「M-1」の範囲にある場合、いくつのサブセットが「i」のモジュロMを有するかをカウントするための解決策である。したがって、総和「N」を「M」とする部分集合の数は、最終配列に含まれることになる。テーブルは実際には 'A'の次の要素を処理するときに更新される1つの行です。 –
@AntonAndell行の各インデックスは、前述したように、「サムインデックス '(mod' M')を持つサブセットの数」を表します。前の行に次の要素をどのように適用できるか考えてみましょうか?それに助けが必要な場合は、私に知らせてください。ここにはヒントがあります:「S [i]で表される各サブセットについて、次の要素で生成できるサブセットの数は「A」で、数はどこに配置されるのでしょうか?そのような部分集合に 'a 'を加えると、その結果mod' M 'を知ることを考慮して、 –
いくつかのコードとベンチマーク、それを書きます。 – jdv