将一个二进制字符串分割成K个子集，使得0和1的出现次数的乘积之和最小化

二进制字符串由一系列二进制数（也称为位，即 0 或 1）组成。它是一种仅使用两个数字的数据编码方法，用于计算机应用程序，其中数据存储和处理使用只能识别两种状态的电子电路。在计算机编程中，二进制字符串经常用于以电子电路易于处理的方式表示数据，例如数字、文本和图像。

方法

方法1.动态规划

方法2.贪心法

方法一：动态规划

为了解决这个困难，我们可以采用动态规划。令 dp [i] [j] 为分为 j 个子集的二进制字符串的前 i 个字符的最小乘积和。通过测试所有可行的分割焦点 k (1 = k I) 并随后注册 dp [i] [j]，我们可以决定 dp[k] [j-1] + cost[k+1] [i] 的基数，其中 cost[k+1] [i] 是将子字符串从 k+1 划分到 I 的费用。这并不是通过复制子字符串中 0 和 1 的数量来确定的。

语法

下面提供了动态编程方法的语法 -

• 创建名为 dp 的二维表，维度为 K+1 x n+1，其中 K 是子集数，n 是二进制字符串的长度。当二进制字符串的前j个字符被分为i个子集时，dp[i][j]反映0和1的乘积的最小和。

• 初始化基本情况-

  • dp[1][j] 是二进制字符串的前 j 个字符的所有 0 和 1 实例的总和。

  • 对于每个 i，dp[i][i] 都为 0（因为分割长度为 i 的字符串时只有一个子集）。

• 使用递推关系查找 2 到 K 中的每个 i 和 i+1 到 n 中的每个 j dp[i][j]： dp[i][j] = min(dp[i-1][k] + 成本[k+1][j] 这里cost[k+1][j]是从k+1到j的子串的所有0和1的乘积。通过迭代从 i-2 到 j-2 的所有可能的 k 值，可以确定 dp[i][j] 的最小值。

• 当二进制字符串被划分为 K 个子集时，dp[K][n] 提供 0 和 1 的乘积的最小和。

算法

步骤 1 - 二进制字符串的边数组 (K+1)* (n+1)。

步骤 2− 将基本情况的初始条件设置为 dp[0][0] = 0，dp[i][0] = 无穷大（i > 0），并且 dp[0][j ] = j > 0 时无穷大。

步骤 3 - 计算从 1 到 n 的每个 i 和从 1 到 K 的每个 j dp[i][j] -

• 取所有此类成本的最小值，如 dp[i][j]。

• 对于从 0 到 i-1 的每个 k，计算将二进制字符串从 k 到 i-1 拆分为 j-1 个子集的成本，并将该子字符串中 0 和 1 的数量相加。

步骤 4 - 提供 dp[n][K] 作为将二进制字符串划分为 K 个子集的最便宜的方法。

示例 1

第一步，我们将所有二进制字符串的可能子字符串相加，并将结果存储在 sum 数组中。将二进制字符串分为 k 个子集（最多第 i 个字符）后，将乘积的最小和存储在 dp 数组中。

#include <iostream>		
#include <cstring>
#include <climits>
using namespace std;

const int MAXN = 105;
const int INF = INT_MAX;

int dp[MAXN][MAXN], sum[MAXN][MAXN];

int main() {
   string s = "1001011101"; 
   int K = 3; 
   int n = s.length();
   memset(dp, 0, sizeof(dp));
   memset(sum, 0, sizeof(sum));
   for (int i = 1; i <= n; i++) {
      sum[i][i] = s[i - 1] - '0';
      for (int j = i + 1; j <= n; j++) {
         sum[i][j] = sum[i][j - 1] + s[j - 1] - '0';
      }
   }
   for (int k = 1; k <= K; k++) {
      for (int i = 1; i <= n; i++) {
         if (k == 1) {  
            dp[i][k] = sum[1][i] * (sum[1][n] - sum[i][n]);
         } else {
           dp[i][k] = INF;
            for (int j = 1; j < i; j++) {
              dp[i][k] = min(dp[i][k], dp[j][k - 1] + sum[j + 1][i] * (sum[1][n] - sum[i][n]));
            }
         }
      }
   }
   cout << "Minimum sum of products: " << dp[n][K] << endl;
   return 0;
}

输出

Minimum sum of products: -2147483624

方法2：贪心法

我们可以首先将二进制字符串分割成 K 个相等的部分。然后可以确定每个组件的成本，并且通过更换附近的组件，我们可以努力降低总体成本。在没有更多可行的交换或不再节省成本之前，我们可以交换附近的部分。

语法

• 给定二进制字符串 s 和整数 K

• 二进制字符串s的长度

int n = s.length(); 

• cut[i] = s 的前 i 位中 1 的数量

vector<int> cut(a+1);
for (int D = 0; D < a; D++) {
   cut[D+1] = cut[D] + (s[D] == '1');
}
vector<int> ft(a+1, 1e9); 
ft[0] = 0;
for (int R = 1; k <= R; R++) {
   for (int D = a; D >= R; D--) {
      for (int j = R-1; j < R; j++) {
         dp[D] = min(ft[D], ft[j] + (cut[D] - cut[j]) * (cut[j] - cut[R-1]));
      }
   }
}

• s 中 0 和 1 的乘积的最小和分为 K 个子集

int ans = ft[a]; 

贪心法算法

第 1 步 - 确定二进制字符串的 0 和 1 计数。

步骤 2 - 从 1 的数字中减去 0 的数字。

步骤 3 - 将二进制字符串分割成 K 个相等的部分。

第 4 步 - 计算每个段中有多少个 0 和 1。

第 5 步 - 从每个段的 1 数字中减去 0 数字。

第 6 步 - 通过添加所有部分产品获得总产品。

步骤 7 - 如果总乘积小于计算步骤 2 中确定的值，则返回段作为解决方案。如果没有，请转至步骤 8。

步骤 8 - 继续，直到通过合并具有最小 0 和 1 乘积之和的相邻段获得 K 个段。

示例 2

接下来，假设 0 和 1 的所有冗余数不为负，通过强调每个字母并将其添加到正在进行的子集中，将字符串分为 K 个子集。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<string> splitBinaryString(string s, int k) {
   vector<int> zeros(s.length()), ones(s.length());
   int zeroCount = 0, oneCount = 0;
   for (int i = s.length() - 1; i >= 0; i--) {
      if (s[i] == '0') zeroCount++;
      else oneCount++;
      zeros[i] = zeroCount;
      ones[i] = oneCount;
   }
   vector<string> subsets(k);
   for (int i = 0; i < k; i++) {
      subsets[i] = "";
      int start = i, end = s.length() - k + i + 1;
      for (int j = start; j < end; j++) {
         int zeroOccurrences = zeros[j] - zeros[start];
         int oneOccurrences = ones[j] - ones[start];
         if (zeroOccurrences * oneOccurrences < 0) break;
         subsets[i] += s[j];
      }
   }
   return subsets;
}
int sumOfProducts(vector<string> subsets) {
   int sum = 0;
   for (string subset : subsets) {
      int zeroCount = count(subset.begin(), subset.end(), '0');
      int oneCount = subset.length() - zeroCount;
      sum += zeroCount * oneCount;
   }
   return sum;
}
int main() {
   string s = "1010110010";
   int k = 3;
   vector<string> subsets = splitBinaryString(s, k);
   int result = sumOfProducts(subsets);
   cout << "Minimum sum of products of occurrences of 0 and 1: " << result << endl;
   return 0;
}

输出

Minimum sum of products of occurrences of 0 and 1: 48

结论

将二进制字符串划分为 K 个子集时，可以使用动态规划来找到 0 和 1 的乘积的最小和。我们可以通过跟踪每个子集大小和每个起始位置的最小成本来快速确定最小成本完整字符串。动态规划方法的时间复杂度为O(K*n2)，其中n为二进制串的长度。