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

Question

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

我的程序使用自下而上的方法找到了最小的差异。该任务要求程序的内存复杂度为θ（s），所以我不使用像传统方法那样使用大小为n * s的2D数组，而是仅使用该数组的两行。在第一行中，我保留了先前处理过的行，因此可以根据先前的解决方案填充第二行。

问题是，通过这种内存优化，我不确定如何填充所有权数组。我知道可以使用n * s数组中的回溯来检索set元素。但是，由于任务的限制，我无法使用该方法，也不知道如何有效地构造所有权表。

是否有一种方法可以有效地找到哪两个元素属于这两个最佳集合中的哪一个，并具有内存复杂度θ（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)中运行的函数，该函数一次运行DP并找出最接近的目标和。

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

反复运行第二个函数以从头到尾挑选所有权数组的每个成员。

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