1

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

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

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

我知道可以使用 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;
}
4

2 回答 2

0

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

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

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

于 2020-03-31T09:39:54.887 回答
0

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

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

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

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

于 2020-03-30T15:52:00.650 回答