Konstruieren Sie aus dem Array gemäß den angegebenen Bedingungen eine binäre Zeichenfolge der Länge K

In diesem Tutorial müssen wir eine Binärzeichenfolge der Länge K so konstruieren, dass sie an ihrem i-ten Index „1“ enthalten sollte, wenn die Summe der Teilmengen gleich I mithilfe von Array-Elementen erreicht werden kann. Wir lernen zwei Möglichkeiten kennen, das Problem zu lösen. Im ersten Ansatz werden wir dynamische Programmiermethoden verwenden, um zu prüfen, ob es möglich ist, dass die Summe der Teilmengen gleich dem Index „I“ ist. Bei der zweiten Methode verwenden wir Bitset, um alle möglichen Summen über Array-Elemente zu finden.

Problemstellung – Wir erhalten ein Array mit N ganzen Zahlen. Zusätzlich erhalten wir eine Ganzzahl M, die die Länge der Binärzeichenfolge darstellt. Wir müssen eine Binärzeichenfolge der Länge M erstellen, die die folgenden Bedingungen erfüllt.

• Das Zeichen am Index „I“ ist 1, wenn wir eine Teilmenge aus dem Array finden können, deren Summe gleich dem Index „I“ ist, andernfalls ist es 0.

• Mein Index beginnt bei 1.

Beispiel Beispiel

Input –  arr = [1, 2] M = 4

Output – 1110

Anleitung

• Die Teilmenge, deren Summe 1 ist, ist {1}.

• Die Teilmenge, deren Summe 2 ist, ist {2}.

• Die Teilmenge, deren Summe 3 ist, ist {1, 2}.

• Wir können keine Teilmenge finden, deren Summe 4 beträgt, also setzen wir 0 in den 4. Index.

Input –  arr = [1, 3, 1] M = 9

Output – 111110000

Anleitung

Wir können alle möglichen Kombinationen erstellen, sodass die Summe zwischen 1 und 5 liegt. Die ersten 5 Zeichen sind also 1 und die letzten 4 Zeichen sind 0.

Input –  arr = [2, 6, 3] M = 6

Output – 011011

Anleitung

Mit Array-Elementen können Sie keine Summe von 1 und 4 erhalten, daher platzieren wir 0 an der ersten und vierten Indexposition.

Methode 1

In dieser Methode verwenden wir dynamische Programmierung, um zu prüfen, ob wir mithilfe von Array-Elementen eine Summe bilden können, die dem Index „I“ entspricht. Wir werden es für jeden Index überprüfen und 1 oder 0 an eine Binärzeichenfolge anhängen.

Algorithmus

• Schritt 1 – Erstellen Sie einen Vektor der Größe N und initialisieren Sie ihn mit einem ganzzahligen Wert. Definieren Sie außerdem eine „bin“-Variable vom Typ string und initialisieren Sie sie mit einer leeren Zeichenfolge.

• Schritt 2 – Verwenden Sie eine for-Schleife, um die Gesamtzahl der Iterationen gleich der Stringlänge zu machen.

• Schritt 3 – Rufen Sie in der for-Schleife die Funktion isSubsetSum() auf, indem Sie das Array N und den Indexwert als Parameter übergeben.

• Schritt 4 – Wenn die Funktion isSubsetSum() „true“ zurückgibt, hängen Sie „1“ an „bin“ an. Andernfalls hängen Sie „0“ an „bin“ an.

• Schritt 5 – Definieren Sie die Funktion isSubsetSum(), um zu prüfen, ob die Summierung mithilfe von Array-Elementen erfolgen kann.

• Schritt 5.1 – Definieren Sie einen zweidimensionalen Vektor mit dem Namen dpTable.

• Schritt 5.2 – Initialisieren Sie „dpTable[i][0]“ auf „true“, da eine Nullsumme immer möglich ist. Hier ist „I“ der Indexwert.

• Schritt 5.3 – Initialisieren Sie „dpTable[0][j]“ auf „false“, da die Summe leerer Arrays nicht möglich ist.

• Schritt 5.4 – Verwenden Sie nun zwei verschachtelte Schleifen. Die erste Schleife iteriert von 1 bis N und die andere Schleife iteriert von 1 bis Summe.

• Schritt 5.5 – Wenn in der for-Schleife der Wert des aktuellen Elements größer als die Summe ist, ignorieren Sie es.

• Schritt 5.6 − Andernfalls schließen Sie Elemente ein oder aus, um die Summe zu erhalten.

• Schritt 5.7 − Geben Sie „dpTable[N][sum]“ mit den Ergebnissen zurück.

Beispiel

#include <iostream>
#include <vector>
using namespace std;
// Function to check if subset-sum is possible
bool isSubsetSum(vector<int> &arr, int N, int sum){
   vector<vector<bool>> dpTable(N + 1, vector<bool>(sum + 1, false));
   
   // Base cases
   for (int i = 0; i <= N; i++)
   
      // If the sum is zero, then the answer is true
      dpTable[i][0] = true;
      
   // for an empty array, the sum is not possible
   for (int j = 1; j <= sum; j++)
      dpTable[0][j] = false;
      
   // Fill the dp table
   for (int i = 1; i <= N; i++){
      for (int j = 1; j <= sum; j++){
      
         // if the current element is greater than the sum, then we can't include it
         if (arr[i - 1] > j)
            dpTable[i][j] = dpTable[i - 1][j];
            
         // else we can either include it or exclude it to get the sum
         else
            dpTable[i][j] = dpTable[i - 1][j] || dpTable[i - 1][j - arr[i - 1]];
      }
   }
   
   // The last cell of the dp table contains the result
   return dpTable[N][sum];
}
int main(){

   // Given M
   int M = 9;
   
   // Creating the vector
   vector<int> arr = {1, 3, 1};
   
   // getting the size of the vector
   int N = arr.size();
   
   // Initializing the string
   string bin = "";
   
   // Making k iteration to construct the string of length k
   for (int i = 1; i <= M; i++){
   
      // if the subset sum is possible, then add 1 to the string, else add 0
      if (isSubsetSum(arr, N, i)){
         bin += "1";
      }
      else{
         bin += "0";
      }
   }
   
   // print the result.
   cout << "The constructed binary string of length " << M << " according to the given conditions is ";
   cout << bin;
   return 0;
}

Ausgabe

The constructed binary string of length 9 according to the given conditions is 111110000

Zeitkomplexität – O(N^3), da die Zeitkomplexität von isSubsetSum() O(N^2) beträgt und wir sie im Treibercode N-mal aufrufen.

Raumkomplexität – O(N^2), da wir in der Funktion isSubsetSum() einen zweidimensionalen Vektor verwenden.

So verwenden Sie Bitset

Bei dieser Methode verwenden wir Bitsätze, um alle möglichen Summenwerte zu finden, indem wir verschiedene Elemente des Arrays kombinieren. Bitset bedeutet hier, dass eine Binärzeichenfolge erstellt wird. Im resultierenden Bitsatz repräsentiert jedes Bit davon, ob die Summe wahrscheinlich einem bestimmten Index entspricht, und wir müssen ihn hier finden.

Algorithmus

• Schritt 1 – Definieren Sie das Array und M. Definieren Sie außerdem die Funktion createBinaryString().

• Schritt 2 – Als nächstes definieren Sie den Satz von Bits mit der gewünschten Länge, wodurch eine Binärzeichenfolge erstellt wird.

• Schritt 3 – Bit[0] auf 1 initialisieren, da eine Summe von 0 immer möglich ist.

• Schritt 4 – Verwenden Sie eine for-Schleife, um die Array-Elemente zu durchlaufen

.

• Schritt 5 – Führen Sie zunächst eine „Bit“-Linksverschiebung an den Array-Elementen durch. Der resultierende Wert wird dann mit dem Bitwert ODER-verknüpft.

• Schritt 6 − Drucken Sie den Wert des Bitsatzes von Index 1 bis M.

Beispiel

#include <bits/stdc++.h>
using namespace std;
// function to construct the binary string
void createBinaryString(int array[], int N, int M){
   bitset<100003> bit;
   
   // Initialize with 1
   bit[0] = 1;
   
   // iterate over all the integers
   for (int i = 0; i < N; i++){
      // perform left shift by array[i], and OR with the previous value.
      bit = bit | bit << array[i];
   }
   
   // Print the binary string
   cout << "The constructed binary string of length " << M << " according to the given conditions is ";
   for (int i = 1; i <= M; i++){
      cout << bit[i];
   }
}
int main(){

   // array of integers
   int array[] = {1, 4, 2};
   int N = sizeof(array) / sizeof(array[0]);
   
   // value of M, size of the string
   int M = 8;
   createBinaryString(array, N, M);
}

Ausgabe

The constructed binary string of length 8 according to the given conditions is 11111110

Zeitkomplexität – O(N), weil wir eine einzelne for-Schleife verwenden.

Raumkomplexität – O(N), weil wir den Wert des Bitsatzes speichern.

Fazit

Hier haben wir die zweite Methode optimiert, die hinsichtlich der räumlichen und zeitlichen Komplexität besser ist als die erste Methode. Allerdings kann die zweite Methode für Anfänger schwierig zu verstehen sein, wenn Sie keine Ahnung von Bitsätzen haben.

Das obige ist der detaillierte Inhalt vonKonstruieren Sie aus dem Array gemäß den angegebenen Bedingungen eine binäre Zeichenfolge der Länge K. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!