Bina rentetan perduaan panjang K daripada tatasusunan mengikut keadaan yang diberikan

Dalam tutorial ini, kita perlu membina rentetan binari panjang K, yang sepatutnya mengandungi "1" pada indeks ke-i jika jumlah subset sama dengan I boleh dicapai menggunakan elemen tatasusunan. Kami akan belajar dua cara untuk menyelesaikan masalah tersebut. Dalam pendekatan pertama, kami akan menggunakan kaedah pengaturcaraan dinamik untuk menyemak sama ada kemungkinan jumlah subset adalah sama dengan indeks "I". Dalam kaedah kedua, kami akan menggunakan bitset untuk mencari semua jumlah yang mungkin melalui elemen tatasusunan.

Pernyataan Masalah - Kami diberi tatasusunan yang mengandungi N integer. Selain itu, kita diberi integer M yang mewakili panjang rentetan binari. Kita perlu mencipta rentetan binari dengan panjang M supaya ia mematuhi syarat berikut.

• Watak pada indeks "I" ialah 1 jika kita boleh mencari subset daripada tatasusunan yang jumlahnya sama dengan indeks "I" jika tidak, ia adalah 0.

• Indeks saya bermula dari 1.

Contoh Contoh

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

Output – 1110

Arahan

• Subset yang jumlahnya bersamaan dengan 1 ialah {1}.

• Subset yang jumlahnya bersamaan dengan 2 ialah {2}.

• Subset yang jumlahnya bersamaan dengan 3 ialah {1, 2}.

• Kami tidak dapat mencari subset yang jumlahnya bersamaan dengan 4, jadi kami meletakkan 0 pada indeks ke-4.

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

Output – 111110000

Arahan

Kita boleh mencipta semua kombinasi yang mungkin supaya jumlahnya adalah antara 1 dan 5. Jadi, 5 aksara pertama ialah 1 dan 4 aksara terakhir ialah 0.

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

Output – 011011

Arahan

Anda tidak boleh mendapatkan jumlah yang sama dengan 1 dan 4 menggunakan elemen tatasusunan, jadi kami meletakkan 0 pada kedudukan indeks pertama dan keempat.

Kaedah 1

Dalam kaedah ini kita akan menggunakan pengaturcaraan dinamik untuk menyemak sama ada kita boleh membina jumlah yang sama dengan indeks 'I' menggunakan elemen tatasusunan. Kami akan menyemaknya untuk setiap indeks dan menambahkan 1 atau 0 pada rentetan binari.

Algoritma

• Langkah 1 - Buat vektor bersaiz N dan mulakan dengan nilai integer. Juga, tentukan pembolehubah "bin" bagi rentetan jenis dan mulakannya dengan rentetan kosong.

• Langkah 2 - Gunakan gelung for untuk menjadikan jumlah bilangan lelaran sama dengan panjang rentetan.

• Langkah 3 - Dalam gelung for, panggil fungsi isSubsetSum() dengan menghantar array N dan nilai indeks sebagai parameter.

• Langkah 4 - Jika fungsi isSubsetSum() kembali benar, tambahkan "1" pada "bin". Jika tidak, tambahkan "0" pada "bin".

• Langkah 5 - Tentukan fungsi isSubsetSum() untuk menyemak sama ada elemen tatasusunan boleh dijumlahkan.

• Langkah 5.1 - Takrifkan vektor dua dimensi bernama dpTable.

• Langkah 5.2 - Mulakan 'dpTable[i][0]' kepada benar kerana jumlah sifar sentiasa mungkin. Di sini, 'I' ialah nilai indeks.

• Langkah 5.3 - Mulakan 'dpTable[0][j]' kepada palsu kerana jumlah tatasusunan kosong tidak boleh dilakukan.

• Langkah 5.4 - Sekarang, gunakan dua gelung bersarang. Gelung pertama lelaran dari 1 ke N dan gelung lain lelaran dari 1 kepada jumlah.

• Langkah 5.5 - Dalam gelung for, jika nilai elemen semasa lebih besar daripada jumlah, abaikan ia.

• Langkah 5.6 − Jika tidak, masukkan atau kecualikan elemen untuk mendapatkan jumlah.

• Langkah 5.7 − Kembalikan 'dpTable[N][sum]' yang mengandungi keputusan.

Contoh

#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;
}

Output

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

Kerumitan masa - O(N^3), kerana kerumitan masa isSubsetSum() ialah O(N^2) dan kami memanggilnya N kali dalam kod pemandu.

Kerumitan ruang - O(N^2), kerana kami menggunakan vektor dua dimensi dalam fungsi isSubsetSum().

Cara menggunakan Bitset

Dalam kaedah ini, kami akan menggunakan set bit untuk mencari semua nilai jumlah yang mungkin dengan menggabungkan elemen tatasusunan yang berbeza. Di sini, bitset bermaksud ia mencipta rentetan binari. Dalam set bit yang terhasil, setiap bit daripadanya mewakili sama ada jumlah itu mungkin sama dengan indeks tertentu, dan kita perlu mencarinya di sini.

Algoritma

• Langkah 1 - Tentukan tatasusunan dan M. Selain itu, tentukan fungsi createBinaryString().

• Langkah 2 - Seterusnya, tentukan set bit panjang yang dikehendaki, yang akan mencipta rentetan binari.

• Langkah 3 - Mulakan bit[0] kepada 1, kerana jumlah 0 sentiasa mungkin.

• Langkah 4 - Gunakan gelung for untuk mengulangi elemen tatasusunan

.

• Langkah 5 - Mula-mula, lakukan operasi anjakan kiri "sedikit" pada elemen tatasusunan. Nilai yang terhasil kemudiannya OR dengan nilai bit.

• Langkah 6 − Cetak nilai set bit dari indeks 1 hingga M.

Contoh

#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);
}

Output

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

Kerumitan masa - O(N) kerana kami menggunakan gelung tunggal.

Kerumitan ruang - O(N) kerana kami menyimpan nilai set bit.

Kesimpulan

Di sini, kami mengoptimumkan kaedah kedua, yang lebih baik daripada kaedah pertama dari segi kerumitan ruang dan masa. Walau bagaimanapun, kaedah kedua mungkin sukar difahami oleh pemula jika anda tidak mempunyai pemahaman tentang set bit.

Atas ialah kandungan terperinci Bina rentetan perduaan panjang K daripada tatasusunan mengikut keadaan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!