根據給定條件，從數組建構一個長度為K的二進位字串

在本教程中，我們需要建構一個長度為K 的二進位字串，如果使用陣列元素可以實現等於I 的子集和，則它的第i 個索引處應包含“1”。我們將學習兩種解決問題的方法。在第一種方法中，我們將使用動態規劃方法來檢查子集和等於索引「I」是否可能。在第二種方法中，我們將使用位集透過陣列元素來尋找所有可能的和。

問題陳述 - 我們給了一個包含 N 個整數的陣列。此外，我們還給出了表示二進位字串長度的整數 M。我們需要建立一個長度為 M 的二進位字串，使其遵循以下條件。

• 如果我們能從陣列中找到總和等於索引「I」的子集，則索引「I」處的字元為 1；否則為 0。

• 我從1開始的索引。

範例範例

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

Output – 1110

說明

• 總和等於 1 的子集是 {1}。

• 總和等於 2 的子集是 {2}。

• 總和等於 3 的子集是 {1, 2}。

• 我們找不到總和等於 4 的子集，因此我們將 0 放在第 4 個索引處。

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

Output – 111110000

說明

我們可以創建所有可能的組合，以使總和在1到5之間。所以，前5個字元是1，最後4個字元是0。

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

Output – 011011

說明

使用陣列元素無法得到等於1和4的和，因此我們將0放置在第一個和第四個索引位置。

方法 1

在這個方法中，我們將使用動態規劃來檢查是否可以使用陣列元素來建構等於索引'I'的總和。我們將為每個索引檢查它，並將1或0附加到一個二進位字串中。

演算法

• 步驟 1 - 建立大小為 N 的向量並使用整數值對其進行初始化。另外，定義字串類型的“bin”變數並使用空字串對其進行初始化。

• 第二步 - 使用for迴圈使總迭代次數等於字串長度。

• 第三步 - 在for迴圈中，透過將陣列N和索引值作為參數來呼叫isSubsetSum()函數。

• 步驟 4 - 如果 isSubsetSum() 函數傳回 true，則將「1」附加到「bin」。否則，將“0”附加到“bin”。

• 第 5 步 - 定義 isSubsetSum() 函數以檢查是否可以使用陣列元素求和。

• 步驟 5.1 - 定義一個名為 dpTable 的二維向量。

• 步驟 5.2 - 將 'dpTable[i][0]' 初始化為 true，因為總和為零總是可能的。這裡，'I' 是索引值。

• 步驟 5.3 - 將 'dpTable [0] [j]' 初始化為 false，因為空數組的和是不可能的。

• 步驟 5.4 - 現在，使用兩個巢狀循環。第一個循環從1到N進行迭代，另一個循環從1到sum進行迭代。

• 步驟 5.5 - 在 for 迴圈中，如果目前元素的值大於總和，則忽略它。

• 步驟 5.6 − 否則，包括或排除元素以獲得總和。

• 步驟 5.7 − 傳回包含結果的 ‘dpTable[N][sum]’。

範例

#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

時間複雜度 - O(N^3)，因為 isSubsetSum() 的時間複雜度為 O(N^2)，我們在驅動程式程式碼中呼叫它 N 次。

空間複雜度 - O(N^2)，因為我們在isSubsetSum()函數中使用了一個二維向量。

使用Bitset的方法

在這種方法中，我們將使用位元集透過組合陣列的不同元素來尋找所有可能的總和值。這裡，bitset 意味著它創建一個二進位字串。在結果位集中，它的每一位都代表總和是否可能等於特定索引，我們需要在這裡找到它。

演算法

• 第 1 步 - 定義陣列和 M。此外，定義 createBinaryString() 函數。

• 第 2 步 - 接下來，定義所需長度的位元集，這將建立一個二進位字串。

• 第三步 - 將bit[0]初始化為1，因為總和為0總是可能的。

• 第 4 步 - 使用 for 迴圈迭代數組元素

#。

• 步驟 5 - 首先，對陣列元素執行「bit」左移操作。然後將結果值與位元值進行或運算。

• 步驟 6 − 從索引 1 到 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

時間複雜度 - O(N)，因為我們使用單一 for 迴圈。

空間複雜度 - O(N)，因為我們儲存了位元集的值。

結論

在這裡，我們優化了第二種方法，從空間和時間複雜度來看，它比第一種方法更好。然而，如果你沒有對位集的了解，第二種方法可能對初學者來說很難理解。

以上是根據給定條件，從數組建構一個長度為K的二進位字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！