Maximal mögliche ausgeglichene binäre Teilstringaufteilung mit höchstens k

Das Array in der Programmiersprache C hat eine feste Größe, was bedeutet, dass Sie die einmal angegebene Größe weder verkleinern noch erweitern können.

Wie wir wissen, ist ein Array eine Menge von Elementen desselben Datentyps, die in einem zusammenhängenden Speicherbereich gespeichert sind.

Gegeben sei ein Array von Werten v[] und ein Binärarray a[]. Das Ziel besteht darin, so viele k Münzen wie möglich zu verwenden, um das Binärarray so weit wie möglich zu unterteilen und gleichzeitig sicherzustellen, dass jedes Segment die gleiche Anzahl von Nullen und hat 1s. i und j sind die Nachbarindizes des geteilten Segments und die Kosten jeder Teilung betragen (v[i] - v[j])2.

Problemstellung

Implementieren Sie ein Programm, das die größtmögliche ausgeglichene Aufteilung binärer Teilzeichenfolgen findet und höchstens k kostet.

Beispiel Beispiel 1

Let the Input array be: 
a: [1,0,0, 1, 0, 0, 1, 1]
The given values be: 
v: [7, 8, 9, 10, 11, 12,13,14]
K: 1

Erhaltene Ausgabe ist: 1

Erklärung

Da der Wert von K 1 ist, können wir einen Schnitt zwischen dem ersten und zweiten Index vornehmen.

In diesem Fall sind [0, 1] und [0, 0, 1, 1] die ausgeglichenen binären Teilzeichenfolgen des Endergebnisses.

Dieser Schnitt kostet (8 - 9)^2 = 1 und 1 = 1.

Beispiel Beispiel 2

Let the Input array be: 
a: [1,0 1, 0, 1, 1, 0,0]
The given values be: 
v: [2, 4, 7, 10, 11, 12, 13, 14]
K: 14

Output obtained is: 2

Erklärung

Der erste Schnitt erfolgt zwischen dem ersten und zweiten Index, also 4 und 7, und kostet uns (4 - 7)^2 = 9, und der zweite Schnitt erfolgt zwischen dem dritten und vierten Index, also 7 und 10, und kostet uns us (7 - 10)^ 2 = 9. Zu diesem Zeitpunkt sind keine weiteren Schnitte möglich. Die ausgeglichenen binären Teilzeichenfolgen, die in diesem Fall entstehen würden, sind [1, 0], [1, 0] und [1, 1, 0 , 0].

Ansatz

Um maximal mögliche ausgeglichene binäre Teilstringaufteilungen mit höchsten Kosten k zu finden, verwenden wir die folgende Methodik.

Hier verfolgen wir einen Top-Down-Ansatz, um dieses Problem zu lösen und maximal mögliche ausgeglichene binäre Teilstringaufteilungen mit höchsten Kosten k zu finden.

Verwenden Sie einen Top-Down-Ansatz, der allgemein als dynamische Programmierung bezeichnet wird. Der Hauptvorteil der dynamischen Programmierung ist die verbesserte Effizienz der einfachen Rekursion. Dynamische Programmierung kann verwendet werden, um jede rekursive Lösung zu optimieren, die wiederholte Aufrufe derselben Eingabe beinhaltet. Um zu vermeiden, dass die Ergebnisse von Teilproblemen später erneut berechnet werden, besteht die Idee darin, sie zu speichern. Mit dieser einfachen Optimierung wird die Zeitkomplexität von polynomisch auf exponentiell reduziert.

Algorithmus

Der Algorithmus zum Finden maximal möglicher ausgeglichener binärer Teilstringaufteilungen mit höchsten Kosten K ist unten angegeben.

• Schritt – Start

• Schritt 2 – Definieren Sie eine zweidimensionale Matrix m

• Schritt 3 – Definieren Sie eine Funktion, um die maximal mögliche ausgeglichene binäre Teilstringaufteilung zu finden.

• Schritt 4 - Definieren Sie die Ganzzahlvariablen „zeroCount“, um die Anzahl der Nullen zu zählen, und „oneCount“, um jeweils die Anzahl der Einsen zu zählen

• Schritt 5 − Definieren Sie eine Ganzzahlvariable cntSplits, um die Anzahl der Teilungen zu zählen

• Schritt 6 – Iterieren Sie über das angegebene Array a

• Schritt 7 − Überprüfen Sie, ob die Anzahl der Nullen gleich der Anzahl der Einsen ist, und speichern Sie dann die maximal mögliche Eins

• Schritt 8 – Angenommen, der Index befindet sich an Position 0, dann finden Sie heraus, ob er 1 oder 0 ist, und erhöhen Sie dann den Zählerstand

• Schritt 9 - Setzen Sie die cntSplits auf Null, wenn die Anzahl von Eins und die Anzahl von Null ungleich sind.

• Schritt 10 – Speichern Sie die resultierenden Werte in einer Matrix

• Schritt 11 − Drucken Sie das gewünschte Ergebnis aus

• Schritt 12 − Stopp

Beispiel: C-Programm

Dies ist eine C-Programmimplementierung des obigen Algorithmus zum Finden der größtmöglichen ausgeglichenen binären Teilstringaufteilung, die höchstens k kostet.

#include <stdio.h>
#include <limits.h>
#include <string.h>
//Define a two-dimensional matrix m
int m[1001][1001];

//Define a function to find maximum possible //balanced binary substring splits
int maxSplits(int a[], int v[], int k, int s) {
   if (k < 0) {
      return INT_MIN;
   }
   if (m[k][s] != -1) {
      return m[k][s];
   }
   
   //Define integer variables to count the number of zeros and ones 
   // Define an integer variable to count the //number of splits
   int zeroCount = 0, oneCount = 0;
   int cntSplits = 0;
   int i;
   
   //Iterating through the given array a
   for (i = s - 1; i > 0; i--) {
      a[i] == 0 ? zeroCount++ : oneCount++;
      
   // check whether the number of zeros is equal to the number of ones, then store the maximum feasible one
      if (zeroCount == oneCount) {
         cntSplits = cntSplits > (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i)) ? cntSplits : (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i));
      }
   }
   
   //Suppose the index is at the position 0, then find whether it is a one or a zero. then increment the count
   if (i == 0) {
      a[0] == 0 ? zeroCount++ : oneCount++;
      
   // set the cntSplits to zero , if count of one and count of zero is unequal.
      if (zeroCount != oneCount) {
         cntSplits = 0;
      }
   }
   
   // store the resultant value in the matrix
   return m[k][s] = cntSplits;
}
int main() {
   int a[] = { 1, 0, 0, 1, 0, 0, 1, 1 };
   int v[] = { 7, 8, 9, 10, 11, 12, 13, 14 };
   int k = 1;
   int s = sizeof(a) / sizeof(a[0]);
   
   //To assign a specific value to a block of memory, we use the memset() function.
   memset(m, -1, sizeof(m));
   printf("%d\n", maxSplits(a, v, k, s));
   return 0;
}

Ausgabe

1

Fazit

Ähnlich können wir die mögliche ausgeglichene binäre Teilstringaufteilung finden, die höchstens K kostet.

In diesem Artikel wird die Herausforderung angegangen, ein Programm dazu zu bringen, die größtmögliche ausgeglichene binäre Teilstringaufteilung bei höchsten Kosten K zu finden.

C-Programmiercode wird hier zusammen mit einem Algorithmus bereitgestellt, um die größtmögliche ausgewogene binäre Teilzeichenfolgenaufteilung zu finden, die höchstens K kostet.

Das obige ist der detaillierte Inhalt vonMaximal mögliche ausgeglichene binäre Teilstringaufteilung mit höchstens k. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!