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

Question

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

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

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

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

有没有办法有效地找到哪些元素属于这两个最优集合中的哪一个，在自下而上的方法中，内存复杂度θ（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

我昨天找到了一个解决方案：

1. 初始化另一个和1元素数组并用零填充它。
2. 在dp数组上迭代时，保存第一个元素的先前数组索引，它允许实现每个总和。例如，对于{4,3,2}，您可以在使用第二个元素时实现总和7，并且您可以使用第一个元素获得4的总和。
3. 得到最小差值后，选择最优集和之一，要么（sum-min）/2，要么Sum-（（sum-min）/2）。
4. 跳转到索引数组中的和，在索引数组中指向的索引中将所有权数组设置为true，然后将元素从和中减去。重复直到总和为零。

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

Answer 2

您可以编写一个在内存< code>O(s)中运行的函数，该函数运行一次DP并找出最接近的目标和。

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

重复运行第二个函数，从末尾到前面挑选出所有权数组的每个成员。

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