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.
Input – arr = [1, 2] M = 4
Output – 1110
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
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
Mit Array-Elementen können Sie keine Summe von 1 und 4 erhalten, daher platzieren wir 0 an der ersten und vierten Indexposition.
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.
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.
#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;
}
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.
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.
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.
#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);
}
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.
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!
Was sind die Definitionen von Arrays?
js-String in Array umwandeln
Der Hauptgrund, warum Computer Binärdateien verwenden
Array-Initialisierungsmethode
c-Array-Initialisierungsmethode
So ermitteln Sie den Maximal- und Minimalwert eines Array-Elements in Java
So entfernen Sie die ersten paar Elemente eines Arrays in PHP
Zusammenfassung der Java-Grundkenntnisse
