数据结构
网络
关系数据库管理系统 (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
