資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究最小化兩個子集和的絕對差
為了最小化兩個子集和的絕對差，我們將一個向量分成兩個子集，即我們將向量的元素分成兩個較小的向量，這樣原始向量的每個元素都屬於兩個較小的向量之一，並且這兩個較小的向量是不相交的。
例如，如果我們有一個向量 v = {1, 2, 3, 4, 5}，那麼 v 分成兩個子集的一種可能的劃分是 S1 = {1, 3, 4} 和 S2 = {2, 5}，其中 v 的每個元素都屬於 S1 或 S2，並且 S1 和 S2 的交集為空集。
本文的目標是以這種方式劃分列表，使子集和的絕對差最小。
問題陳述
手頭的任務是將整數列表劃分為兩個子集 S1 和 S2，使得 S1 元素之和與 S2 元素之和之間的差儘可能小。
示例
輸入
{1, 2, 7}
輸出
4
解釋
具有最小絕對差的兩個分割槽是 {1, 2} 和 {7}。它們的子集和分別是 3 和 7，它們的絕對差是 4。
輸入
{10, 20, 15, 5, 25}
輸出
5
解釋
具有最小絕對差的兩個分割槽是 {10, 20, 5} 和 {15, 25}。它們的子集和分別是 35 和 40，它們的絕對差是 5。
輸入
{1, 1, 1, 1, 1}
輸出
0
解釋
具有最小絕對差的兩個分割槽是 {1, 1, 1} 和 {1, 1, 1}。它們的子集和都是 3，它們的絕對差是 0。
解決方案
這種方法的根本邏輯是使用動態規劃來找到給定整數集的一個子集，其和儘可能接近該集的總和的一半。這是透過建立一個二維布林陣列來實現的，其中 dp[i][j] 表示是否存在一個由前 i 個元素組成的子集，其和為 j。然後，我們檢查是否在該集合的總和的一半的所有值中存在具有該和的子集。最後，我們計算總和與具有最接近總和一半的和的子集的兩倍和之間的最小絕對差。
給定程式的解決方案方法包括以下步驟：
計算輸入陣列中所有元素的和。
建立一個大小為 (n+1)x(range+1) 的二維布林向量，並將所有值初始化為 false，其中 n 是輸入陣列的大小，range 是所有元素的和。
將 dp[i][0] 的值設定為 true，i 的範圍為 0 到 n。
遍歷二維布林向量的行和列，並將 dp[i][j] 的值設定為 dp[i-1][j] 和 dp[i-1][j-arr[i-1]] 的邏輯或，其中 arr 是輸入陣列，i 是當前行，j 是當前列。
建立一個向量來儲存子集和的有效值，即 dp[n][j] 為真的 j 值。
遍歷 range 的一半，並將子集和的所有有效值新增到有效向量中。
遍歷有效向量，並將 mini 的值設定為 mini 和 (range - (2 * valid[i])) 的最小值，其中 mini 初始化為整數的最大值。
將 mini 的值作為輸入陣列的兩個子集分割槽之間的最小絕對差返回。
演算法
函式 minDifference()
初始化 range = 0
對於 i 從 0 到 n - 1
range = range + arr[i]
初始化 dp 矩陣
對於 i 從 0 到 n
設定 dp[i][0] = true
對於 i 從 1 到 n
對於 j 從 1 到 range
如果 arr[i - 1] <= j
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
否則
dp[i][j] = dp[i - 1][j];
初始化布林向量 valid
對於 i 從 0 到 range / 2
如果 (dp[n][i] == true)
valid.push_back(i);
初始化 mini = INT_MAX;
對於 i 從 0 到 valid.size() - 1
mini = min (mini, range - (2 * valid[i]))
返回 mini
函式 main()
初始化整數向量 a
初始化 n = a.size();
函式呼叫 minDifference(a, n);
列印結果
示例：C++ 程式
下面的 C++ 程式使用動態規劃方法來查詢陣列中 2 個子集和之間的最小絕對差。minDifference() 函式計算列表中所有元素的總和。然後，我們初始化並填充 dp 矩陣。我們建立一個包含所有可能的子集和的向量 valid，然後返回答案。
// C++ program to return the minimum absolute difference between 2 subset partitions of array
#include <bits/stdc++.h>
using namespace std;
// function to calculate minimum difference of subset sums
int minDifference(vector<int> arr, int n) {
// Calculate the range of the array
int range = 0;
for (int i = 0; i < n; i++) {
range += arr[i];
}
// Initialize the dp matrix
vector<vector<bool>> dp(n + 1, vector<bool>(range + 1, 0));
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
// Fill the dp matrix
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= range; j++) {
if (arr[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
// Find the valid subset sums
vector<int> valid;
for (int i = 0; i <= range / 2; i++) {
if (dp[n][i] == true) {
valid.push_back(i);
}
}
// Calculate the minimum absolute difference
int mini = INT_MAX;
for (int i = 0; i < valid.size(); i++) {
mini = min(mini, range - (2 * valid[i]));
}
return mini;
}
// driver code
int main() {
// Input array
vector<int> a = {1, 2, 7};
int n = a.size();
// Calculate the minimum subset difference
int result = minDifference(a, n);
cout << "Minimum Subset Difference is: " << result << endl;
return 0;
}
輸出
Minimum Subset Difference is: 4
時間和空間複雜度分析
時間複雜度：O(n2)
該程式使用巢狀迴圈來填充 dp 矩陣，因此 dp 填充步驟的時間複雜度為 O(n * range)。
該程式使用迴圈來查詢有效的子集和，因此子集和檢查步驟的時間複雜度為 O(range/2)。
該程式使用迴圈來計算最小絕對差，因此此步驟的時間複雜度為 O(valid.size())。
因此，該程式的總體時間複雜度為 O(n * range + range/2 + valid.size())。
空間複雜度：O(n2)
該程式使用大小為 (n+1)x(range+1) 的二維布林陣列 dp，因此 dp 矩陣的空間複雜度為 O(n * range)。
該程式使用向量 valid 來儲存有效的子集和，因此有效向量的空間複雜度為 O(range/2)。
因此，該程式的總體空間複雜度為 O(n * range)。
結論
在本文中，我們討論了一種動態規劃方法，用於查詢陣列的 2 個分割槽子集之間的絕對最小差。藉助合適的示例，對問題陳述進行了明確的定義。本文還詳細討論瞭解決方案方法、演算法、C++ 程式程式碼以及時間和空間複雜度。
瀏覽量：318
