資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究將二進位制字串分割成K個子集，使0和1出現次數的乘積之和最小
二進位制字串是由一系列二進位制數字（也稱為位元）組成的，這些數字要麼是0，要麼是1。這是一種使用只有兩個數字的編碼資料的方法，適用於計算機應用程式，其中資料儲存和處理使用只能識別兩種狀態的電子電路。在計算機程式設計中，二進位制字串經常用於以電子電路易於處理的方式表示資料，例如數字、文字和影像。
方法
方法1. 動態規劃
方法2. 貪婪演算法
方法1：動態規劃
為了解決這個問題，我們可以使用動態規劃。令dp[i][j]為將二進位制字串的前i個字元分成j個子集的最小乘積和。透過測試所有可能的分割點k（1 ≤ k < i），然後計算dp[i][j]，我們可以根據dp[k][j-1] + cost[k+1][i]來確定dp[i][j]的值，其中cost[k+1][i]是將從k+1到i的子串分割的代價。代價由子串中0和1的數量的乘積確定。
語法
下面提供動態規劃方法的語法：
建立一個名為dp的二維表，其維度為K+1乘以n+1，其中K是子集的數量，n是二進位制字串的長度。當二進位制字串的前j個字元被分成i個子集時，dp[i][j]表示0和1的乘積之和的最小值。
初始化邊界條件：
dp[1][j]是二進位制字串前j個字元中所有0和1例項的乘積和。
對於每個i，dp[i][i]為0（因為當分割長度為i的字串時，只有一個子集）。
使用遞迴關係查詢每個i（從2到K）和每個j（從i+1到n）的dp[i][j]：dp[i][j] = min(dp[i-1][k] + cost[k+1][j]，其中cost[k+1][j]是從k+1到j的子串中所有0和1的乘積。可以透過迭代所有可能的k值（從i-2到j-2）來找到dp[i][j]的最小值。
當二進位制字串被分成K個子集時，dp[K][n]給出0和1乘積和的最小值。
演算法
步驟1 - 建立一個 (K+1)*(n+1) 維的陣列來儲存二進位制字串的分割結果。
步驟2 - 將邊界條件初始化為 dp[0][0] = 0, i > 0 時 dp[i][0] = 無窮大, j > 0 時 dp[0][j] = 無窮大。
步驟3 - 計算每個 i (從 1 到 n) 和每個 j (從 1 到 K) 的 dp[i][j]：
將所有此類代價的最小值作為 dp[i][j]。
對於每個 k (從 0 到 i-1)，計算將二進位制字串從 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 分割成 K 個子集後，0 和 1 的乘積的最小和
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 * n^2)，其中n是二進位制字串的長度。
瀏覽量：113
