分区问题 - 使用最少的内存查找集合的元素

Question

我必须使用动态规划解决经典的分区问题。我有一个正整数数组作为输入，其中 n 是整数的数量，s 是这些整数的总和，我需要找到可以使用输入元素构造的两个集合之间的最小差异。我还需要输出一个名为 "ownership" 的布尔数组，其大小与输入数组相同，它提供元素是否属于第一或第二最优集的信息。例如，如果所有权数组中的 i-th 值为真，则输入数组的 i-th 元素属于第一个集合。

我的程序使用自下而上的方法找到最小差异。该任务要求程序的内存复杂度为 θ(s)，因此不要像经典中那样使用大小为 n*s 的二维数组方法，我只使用该数组的两行。第一行我保留了之前处理过的行，所以我可以根据之前的解决方案填充第二行。

问题是，通过这种内存优化，我不确定应该如何填充所有权数组。

我知道可以在 n*s 数组中使用回溯来检索集合元素。但是，由于任务限制，我无法使用该方法，而且我不知道如何有效地构建所有权 table。

有没有一种方法可以有效地找到哪些元素属于这两个最佳集合中的哪一个，同时限制内存复杂度 θ(s) 和时间复杂度 O(n*s) 在自下而上的方法？

我当前的 C# 代码：

 public int SetsMinimum(int[] tab, out bool[] ownership)
 {
    int n = tab.Length;
    int sum = 0;
    foreach (int v in tab) sum += v;
    ownership = new bool[n];
    bool[,] dp = new bool[2, sum + 1];
    int min = sum;
    dp[0, 0] = true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= sum; j++)
        {
            dp[1,j] = dp[0,j];
            if (j - tab[i - 1]>=0)
            {
                dp[1, j] = dp[0, j - tab[i - 1]];
            }     
        }
        for(int j=0;j<sum;j++)
        {
            if (dp[1, j])
            {
                int cMin = Math.Abs((sum - j) - j);
                if (min>cMin)
                {
                    min = cMin;
                }
            }    
            dp[0, j] = dp[1, j];
        }
    }
    return min;
}

Answer 1

你可以写一个运行内存O(s)的函数，运行s DP一次，找出最接近的目标总和。

您可以编写一个函数，它运行在内存中 O(s) 运行 DP 一次，并找出所有权数组中的最后一个值是否必须为 true 或 false达到该目标金额。

运行第二个函数从头到尾重复取出所有权数组的每个成员。

这将占用内存 O(s) 和时间 O(s * n^2)。（因为你运行 n DP。）与通常的 DP 方法相反，它需要内存 O(s * n) 和时间 O(s * n)。

Answer 2

我昨天找到了解决办法：

初始化另一个包含 sum+1 个元素的数组并用零填充它。
遍历dp数组时，保存在第一个元素的前一个数组索引中，允许实现每一个和。例如，对于 {4,3,2}，当您使用第二个元素时，您可以获得总和 7，而您可以使用第一个元素获得 4 的总和。
获得最小差异后，选择一个最优集合总和，(sum-min)/2或sum-((sum-min)/2)。
跳转到索引数组求和，在索引数组指向的索引中设置所有权数组为真，然后从求和中减去元素。重复直到你的总和为零。

这种方法只会选择必要的元素来构造其中一个集合和，并且它将在 O(n*s) 时间内工作，因为索引数组可以在期间填充自下而上的方法。

分区问题 - 使用最少的内存查找集合的元素

Partition problem - finding elements of the set using minimal memory

memory

algorithm

dynamic-programming

bottom-up

partition