Construire une chaîne binaire de longueur K à partir du tableau selon les conditions données

Dans ce tutoriel, nous devons construire une chaîne binaire de longueur K telle qu'elle contienne "1" à son i-ème index si la somme des sous-ensembles égale à I peut être obtenue à l'aide d'éléments de tableau. Nous apprendrons deux façons de résoudre le problème. Dans la première approche, nous utiliserons des méthodes de programmation dynamique pour vérifier s'il est possible que la somme des sous-ensembles soit égale à l'indice "I". Dans la deuxième méthode, nous utiliserons bitset pour trouver toutes les sommes possibles à travers les éléments du tableau.

Énoncé du problème - On nous donne un tableau contenant N entiers. De plus, on nous donne un entier M représentant la longueur de la chaîne binaire. Nous devons créer une chaîne binaire de longueur M telle qu'elle obéisse aux conditions suivantes.

• Le caractère à l'index "I" est 1 si l'on peut trouver un sous-ensemble du tableau dont la somme est égale à l'index "I" sinon il est 0 ;

• Mon index commence à 1.

Exemple Exemple

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

Output – 1110

Instructions

• Le sous-ensemble dont la somme est égale à 1 est {1}.

• Le sous-ensemble dont la somme est égale à 2 est {2}.

• Le sous-ensemble dont la somme est égale à 3 est {1, 2}.

• Nous ne trouvons pas de sous-ensemble dont la somme est égale à 4, nous mettons donc 0 au 4ème index.

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

Output – 111110000

Instructions

Nous pouvons créer toutes les combinaisons possibles pour que la somme soit comprise entre 1 et 5. Ainsi, les 5 premiers caractères valent 1 et les 4 derniers caractères valent 0.

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

Output – 011011

Instructions

Vous ne pouvez pas obtenir une somme égale à 1 et 4 en utilisant des éléments de tableau, nous plaçons donc 0 aux première et quatrième positions d'index.

Méthode 1

Dans cette méthode, nous utiliserons la programmation dynamique pour vérifier si nous pouvons construire une somme égale à l'index 'I' à l'aide d'éléments de tableau. Nous allons le vérifier pour chaque index et ajouter 1 ou 0 à une chaîne binaire.

Algorithme

• Étape 1 - Créez un vecteur de taille N et initialisez-le avec une valeur entière. Définissez également une variable "bin" de type chaîne et initialisez-la avec une chaîne vide.

• Étape 2 - Utilisez une boucle for pour rendre le nombre total d'itérations égal à la longueur de la chaîne.

• Étape 3 - Dans la boucle for, appelez la fonction isSubsetSum() en passant le tableau N et la valeur d'index comme paramètres.

• Étape 4 - Si la fonction isSubsetSum() renvoie vrai, ajoutez "1" à "bin". Sinon, ajoutez « 0 » à « bin ».

• Étape 5 - Définissez la fonction isSubsetSum() pour vérifier si les éléments du tableau peuvent être additionnés.

• Étape 5.1 - Définissez un vecteur bidimensionnel nommé dpTable.

• Étape 5.2 - Initialisez 'dpTable[i][0]' à true car une somme nulle est toujours possible. Ici, « I » est la valeur de l'index.

• Étape 5.3 - Initialisez 'dpTable[0][j]' sur false car la somme des tableaux vides n'est pas possible.

• Étape 5.4 - Maintenant, utilisez deux boucles imbriquées. La première boucle parcourt de 1 à N et l’autre boucle parcourt de 1 à somme.

• Étape 5.5 - Dans la boucle for, si la valeur de l'élément actuel est supérieure à la somme, ignorez-la.

• Étape 5.6 − Sinon, incluez ou excluez des éléments pour obtenir la somme.

• Étape 5.7 - Renvoie 'dpTable[N][sum]' contenant les résultats.

Exemple

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

Sortie

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

Complexité temporelle - O(N^3), car la complexité temporelle de isSubsetSum() est O(N^2) et nous l'appelons N fois dans le code du pilote.

Complexité spatiale - O(N^2), car nous utilisons un vecteur bidimensionnel dans la fonction isSubsetSum().

Comment utiliser Bitset

Dans cette méthode, nous utiliserons des jeux de bits pour trouver toutes les valeurs de somme possibles en combinant différents éléments du tableau. Ici, bitset signifie qu'il crée une chaîne binaire. Dans l'ensemble de bits résultant, chaque bit représente si la somme est susceptible d'être égale à un index spécifique, et nous devons le trouver ici.

Algorithme

• Étape 1 - Définissez le tableau et M. De plus, définissez la fonction createBinaryString().

• Étape 2 - Ensuite, définissez l'ensemble de bits de la longueur souhaitée, qui créera une chaîne binaire.

• Étape 3 - Initialisez bit[0] à 1, puisqu'une somme de 0 est toujours possible.

• Étape 4 - Utilisez une boucle for pour parcourir les éléments du tableau

.

• Étape 5 - Tout d'abord, effectuez une opération de décalage vers la gauche "bit" sur les éléments du tableau. La valeur résultante est ensuite combinée en OU avec la valeur du bit.

• Étape 6 - Imprimez la valeur du bit défini de l'index 1 à M.

Exemple

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

Sortie

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

Complexité temporelle - O(N) car nous utilisons une seule boucle for.

Complexité spatiale - O(N) car nous stockons la valeur de l'ensemble de bits.

Conclusion

Ici, nous avons optimisé la deuxième méthode, qui est meilleure que la première méthode en termes de complexité spatiale et temporelle. Cependant, la deuxième méthode peut être difficile à comprendre pour les débutants si vous ne comprenez pas les jeux de bits.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!