DP Lösung zu finden, wenn es Gruppe von Zahlen ist, die durch M teilbar ist

Question

Nehmen wir an, wir Zahl N haben, so dass 0 < N < = 10^6 und 2 < = M < = 10^3 und Anordnung von N Elementen a [1], a [2], ... a [N] (0 < = a [i] < = 10^9) \

Jetzt müssen wir überprüfen, ob wir eine Gruppe von Zahlen aus der wählen können Array so, dass ihre Summe durch M teilbar ist und "JA" oder "NEIN" ausgegeben wird.

Hier sind zwei Beispiele:

N = 3, M = 5 a = {1,2,3} Antwort = "YES"

N = 4, M = 6 a = {3, 1,1,3} answer = "JA"

danke im voraus.

Answer 1

C++ Lösung.

//declare dp array of boolean values of size M 
bool dp[M] = {0}; // init with fasle values 
for(int i = 0; i < N; i++) { 
    bool ndp[M] = {0}; // init temporary boolean array 
    ndp[a[i] % M] = 1; // add a subset with one a[i] element 
    for(int j = 0; j < M; j++) 
     if(dp[j]) { // if we may find a subset of elements with sum = j (modulo M) 
      ndp[j] = 1; // copy existing values 
      ndp[(j + a[i]) % M] = 1; // extend the subset with a[i], which will give a sum = j + a[i] (modulo M) 
     } 
    // copy from ndp to dp before proceeding to the next element of a 
    for(int j = 0; j < M; j++) dp[j] = ndp[j]; 
} 

//check dp[0] for the answer 

wird der Algorithmus Komplexität O (N * M) sein, die in Ihrem Fall ist O (10)

Edit: Added ndp[a[i] % M] = 1; Linie um dp zu machen [j] wird immer von Null verschieden.

---

Es könnte eine weitere Alternative O (M * M * log (M) + N) sein Lösung in Ihrem Fall die O (10) (aber mit großen Konstante) ist.

Beachten Sie, dass, wenn er die a[i] durch a[i] % M ersetzen die Problembeschreibung nicht ändert. Lässt die Anzahl der a[i] Elemente zählen, die den spezifischen Rest j nach Teilung auf M geben. Wenn aus irgendeinem Rest j wir k Elemente in a gefunden, dann können wir die folgenden Summen von Teilmengen erzeugen (das kann einzigartigen Rest produzieren)

j, 2 * j % M, 3 * j % M ... k * j % M

Beispiel: lassen M = 6 und für Rest 2 fanden wir 5 Elemente in a . Dann haben wir die folgenden einzigartigen Summen von Untergruppen:

2 % 6, 2 * 2 % 6, 3 * 2 % 6, 4 * 2 % 6, 5 * 2 % 6
das ist 0, 2, 4
speichern diese Informationen in Form boolean {1, 0, 1, 0, 1, 0}

Allenfalls wir M solche Gruppen haben, die M -Größe Bool Array möglicher Reste erzeugen .

Als nächstes müssen wir alle möglichen Teilmengen finden, die erscheinen können, wenn wir Elemente aus verschiedenen Gruppen nehmen werden. Nehmen wir an, dass wir zwei Bool-Restarrays a und b zusammenführen, wenn wir ein neues Array c einführen können, das alle möglichen Restsummen von Elementen aus der Teilmenge von a und b enthalten wird.Naive Ansatz erfordert, dass wir zwei verschachtelte Schleifen über a und b geben O (M) Zusammenführungszeit Komplexität.

Wir können die Komplexität O (M * log (M)) mit schnelle Fourier-Transformation algo reduzieren. Jedes Array hat eine bool Polynom Σ _{a i * x}ⁱ wobei die Koeffizienten a _i aus bool Array genommen. Wenn wir zwei Arrays zusammenführen wollen, können wir einfach ihre Polynome multiplizieren.

Insgesamt complxity ist O (M * log (M)) wie wir M solche Verschmelzungen zu machen brauchen.