在本教程中，我们需要构造一个长度为 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 #include using namespace std;// Function to check if subset-sum is possiblebool isSubsetSum(vector &arr, int N, int sum){ vector<vector> dpTable(N + 1, vector(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 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 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 using namespace std;// function to construct the binary stringvoid createBinaryString(int array[], int N, int M){ bitset 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的二进制字符串的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444768.html
微信扫一扫 
支付宝扫一扫 
