Cari panjang subset terpanjang yang terdiri daripada A 0s dan B 1s daripada tatasusunan rentetan

Dalam masalah ini, kita perlu mencari subset terpanjang yang mengandungi paling banyak A 0s dan B1s. Apa yang perlu kita lakukan ialah mencari semua subset yang mungkin menggunakan elemen tatasusunan dan cari subset terpanjang yang mengandungi paling banyak A 0 dan B1 .

Dalam tutorial ini, pertama, kita akan mempelajari kaedah rekursif untuk menyelesaikan masalah. Selepas itu, kami akan menggunakan kaedah pengaturcaraan dinamik untuk mengoptimumkan kod.

Pernyataan Masalah - Kami diberi tatasusunan yang mengandungi N rentetan binari. Selain itu, kami diberi integer A dan B. Kita perlu mencipta subset terpanjang menggunakan rentetan binari yang diberikan supaya ia tidak mengandungi lebih daripada A 0 dan B1.

Contoh

Input –  arr = {"101", "0", "101", "0", "1"}, A = 2, B = 1

Output – 3

Penerangan

Subset terpanjang ialah { "0", "0", "1"}, yang mengandungi 2 0s dan 1 1.

Input –  arr = {"0", "101", "0", "1"}, A = 3, B = 3

Output – 3

Penerangan

Subset terpanjang ialah {"0", "101", "0", "1"}, 3 0s dan 3 1s.

Kaedah 1

Dalam bahagian ini, kita akan mempelajari kaedah mudah menggunakan rekursi. Kami akan membina semua subset yang mungkin menggunakan elemen tatasusunan dan mencari subset terpanjang yang mengandungi A 0 dan B 1 .

Algoritma

• Langkah 1 - Tentukan fungsi countZeros() untuk mengira jumlah bilangan sifar dalam rentetan binari yang diberikan.

• Langkah 1.1 - Mulakan pembolehubah "kira" kepada sifar.

• Langkah 1.2 - Gunakan gelung for untuk lelaran melalui rentetan.

• Langkah 1.3 - Jika aksara pada indeks ke-i ialah "0", maka tambahkan nilai "cnt" sebanyak 1.

• Langkah 1.2 - Kembalikan nilai pembolehubah "cnt".

• Langkah 2 - getMaxSubsetLen() mengembalikan nilai integer dan mengambil vektor arr, int A, int B dan indeks sebagai parameter.

• Langkah 3 - Tentukan kes asas dalam fungsi. Mengembalikan 0 jika indeks sama dengan saiz vektor, atau jika nilai A dan B kedua-duanya adalah sifar.

• Langkah 4 - Sekarang, kira jumlah bilangan sifar dalam rentetan pada indeks.

• Langkah 5 - Tolak jumlah nombor 1 daripada panjang rentetan untuk mendapatkan jumlah nombor 1.

• Langkah 6 - Mulakan pembolehubah "pertama" kepada 0.

• Langkah 7 - Mengandungi rentetan binari semasa jika jumlah nombor 0 dan 1 masing-masing kurang daripada A dan B. Menyimpan 1 + nilai pulangan bagi panggilan fungsi rekursif. Apabila membuat panggilan rekursif, 0 dan 1 ditolak daripada A dan B.

• Langkah 8 - Kecualikan rentetan semasa dan simpan nilai yang terhasil dalam pembolehubah "kedua".

• Langkah 9 - Kembalikan nilai maksimum yang pertama dan kedua.

Contoh

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int countZeros(string s){

   // initialize count variable to 0
   int count = 0;
   
   // traverse the string
   for (int i = 0; i < s.size(); i++){
   
      // if the current character is 0, the increment count
      if (s[i] == '0'){
         count++;
      }
   }
   
   // return count
   return count;
}

// recursive function to find the maximum length of a subset of strings according to the given condition.
int getMaxSubsetLen(vector<string> arr, int A, int B, int index){

   // base case
   // if all the strings are traversed, or A + B becomes 0
   if (index == arr.size() || A + B == 0){
      return 0;
   }
   
   // total number of 0's in arr[index] string
   int zero = countZeros(arr[index]);
   
   // total number of 1's in arr[index] string
   int one = arr[index].size() - zero;
   
   // Stores the length of the subset, if arr[i] is included.
   int first = 0;
   
   // if the number of 0's and 1's in arr[index] is less than or equal to A and B, respectively, then include the string
   if (zero <= A && one <= B){
      first = 1 + getMaxSubsetLen(arr, A - zero, B - one, index + 1);
   }
   
   // Stores the length of the subset, if arr[i] is not included.
   int second = getMaxSubsetLen(arr, A, B, index + 1);
   
   // return the maximum of the first and second
   return max(first, second);
}

// Driver Code
int main(){
   vector<string> arr = {"101", "0", "101", "0", "1"};
   int A = 2, B = 1;
   cout << "The maximum length of the subset consisting at most A 0s and B 1s is - " <<getMaxSubsetLen(arr, A, B, 0);
   return 0;
}

Output

The maximum length of the subset consisting at most A 0s and B 1s is - 3

Kerumitan masa - O(2N), kerana kami menemui semua subset yang mungkin menggunakan elemen tatasusunan N.

Kerumitan ruang - O(1)

Kaedah 2

Kami telah mengoptimumkan kaedah di atas dalam bahagian ini. Kami menggunakan kaedah pengaturcaraan dinamik untuk menyelesaikan masalah ini. Ia menyimpan hasil keadaan sebelumnya untuk mengurangkan kerumitan masa masalah.

Algoritma

• Langkah 1 - Tentukan fungsi countZeros() untuk mengira jumlah bilangan sifar dalam rentetan binari tertentu, seperti yang kita lakukan dalam kaedah di atas.

• Langkah 2 - Buat vektor 3 dimensi bersaiz A x B x N untuk menyimpan hasil keadaan sebelumnya. Dalam senarai, kami akan menyimpan panjang subset pada indeks "I" apabila jumlah 0 sama dengan A dan 1 sama dengan B. Selain itu, hantarkannya sebagai hujah kepada fungsi getMaxSubsetLen().

• Langkah 3 - Tentukan kes asas seperti yang kita lakukan dalam kaedah di atas.

• Langkah 4 - Jika nilai dpTable[A][B][index] lebih besar daripada 0, ini bermakna status telah dikira dan nilainya adalah dikembalikan.

• Langkah 5 - Kira jumlah bilangan 0 dan 1 dalam rentetan semasa.

• Langkah 6 - Dapatkan nilai yang terhasil termasuk dan tidak termasuk rentetan semasa.

• Langkah 7 - Gunakan fungsi max() untuk mendapatkan nilai maksimum bagi yang pertama dan kedua dan simpannya dalam dpTable[A][B][ index] Return kepada

Contoh

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int countZeros(string s){

   // initialize count variable to 0
   int count = 0;
   
   // traverse the string
   for (int i = 0; i < s.size(); i++){
   
      // if the current character is 0, the increment count
      if (s[i] == '0'){
         count++;
      }
   }
   
   // return count
   return count;
}

// recursive function to find the maximum length of a subset of strings according to the given condition.
int getMaxSubsetLen(vector<string> array, int A, int B, int index, vector<vector<vector<int>>> &dpTable){

   // base case
   if (index == array.size() || A + B == 0){
      return 0;
   }
   
   // return if already calculated
   if (dpTable[A][B][index] > 0){
      return dpTable[A][B][index];
   }
   
   // total number of 0's in the current string
   int zero = countZeros(array[index]);
   
   // total number of 1's in the current string
   int one = array[index].size() - zero;
   
   // to store the length of the subset can be formed by including the current string
   int first = 0;
   
   // if the total number of 0's and 1's in the current string is less than or equal to A and B, respectively
   if (zero <= A && one <= B){
      first = 1 + getMaxSubsetLen(array, A - zero, B - one, index + 1, dpTable);
   }
   
   // to store the length of the subset can be formed by excluding the current string
   int second = getMaxSubsetLen(array, A, B, index + 1, dpTable);
   
   // store the maximum of the first and second, and return
   return dpTable[A][B][index] = max(first, second);
}
int main(){
   vector<string> arr = {"101", "0", "101", "0", "1"};
   int A = 2, B = 1;
   vector<vector<vector<int>>> dpTable(A + 1, vector<vector<int>>(B + 1, vector<int>(arr.size() + 1, 0)));
   cout << "The maximum length of the subset consisting at most A 0s and B 1s is - " << getMaxSubsetLen(arr, A, B, 0, dpTable);
   return 0;
}

Output

The maximum length of the subset consisting at most A 0s and B 1s is - 3

Kerumitan masa - O(A*B*N), kerana kita perlu mengisi senarai 3D untuk mendapatkan hasilnya.

Kerumitan Ruang - O(A*B*N) kerana kami menggunakan senarai 3D untuk kaedah pengaturcaraan dinamik.

Atas ialah kandungan terperinci Cari panjang subset terpanjang yang terdiri daripada A 0s dan B 1s daripada tatasusunan rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!