C++ 最小化两个子集和的绝对差

为了最小化两个子集和的绝对差，我们将一个向量分成两个子集，即将向量的元素分成两个较小的向量，使得原始向量的每个元素都属于其中一个较小的向量，并且这两个较小的向量是不重叠的。

例如，如果我们有一个向量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}

输出

解释

两个绝对差最小的分区是{1, 2}和{7}。它们的子集和分别为3和7，它们的绝对差为4。

输入

{10, 20, 15, 5, 25}

输出

解释

最小绝对差的两个分区是{10, 20, 5}和{15, 25}。它们的子集和分别为35和40，它们的绝对差是5。

输入

{1, 1, 1, 1, 1}

输出

解释

具有最小绝对差的两个分区是{1, 1, 1}和{1, 1, 1}。它们的子集和都是3，它们的绝对差是0。

解决方法

该方法的基本逻辑是使用动态规划找出给定整数集合的一个子集，使得子集的和尽可能接近集合总和的一半。通过创建一个二维布尔数组，其中dp[i][j]表示是否存在一个和为j的前i个元素的子集。然后，我们检查所有值，直到集合总和的一半是否存在一个和为该值的子集。最后，我们计算总和与最接近集合总和一半的子集的两倍和之间的最小绝对差。

给定程序的解决方法包括以下步骤：

计算输入数组中所有元素的和。
创建一个大小为(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]]的逻辑OR，其中arr是输入数组，i是当前行，j是当前列。
创建一个向量来存储有效的子集和值，即dp[n][j]为true的j的值。
循环遍历范围的一半，并将所有有效的子集和值添加到有效向量中。
循环遍历有效向量，并将mini的值设置为mini和(范围 – (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];

初始化 boolean 向量 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()
- 初始化 integer 向量 a
- 初始化 n = a.size();
- 调用函数 minDifference(a, n);
- 打印结果

例子：C++ 程序

下面的 C++ 程序使用动态规划的方法来找到数组中两个子集和的最小绝对差。函数 minDifference() 计算列表中所有元素的总和。然后，我们初始化并填充 dp 矩阵。我们创建一个 vector 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;
}