使用分而治之技术的最小子向量大小 k

Question

早上好，我有问题要解决：

你有一个大小为n的向量，你想找到一个大小为m的子向量，并且它的元素之和是最小的

这个工作原理的一个例子是： see example of operation 其中最小子向量为：{1,3,1} 总和为 5

我需要通过蛮力（滑动 windows 解释如下）和分而治之的技术来分析这个问题。然后我会写一个对比报告，说明滑动windows效果会好很多。本文是针对算法比较的大学项目。但我需要使用 D&C 显式构建它。

我已经按如下方式完成了，但是我在基本情况和返回最小总和子向量方面遇到了问题。


// Function to find the minimum between two numbers
int min(int a, int b) { return (a < b)? a : b; }

// Function to find the minimum between three numbers
int min(int a, int b, int c) { return min(min(a, b), c); }

// Function to find the minimum sum that passes through the center of the vector
int minSumCenter(int v[], int l, int center, int h)
{

    // Elements to the left of the center
    int sum = 0;
    int left_sum = INT_MAX;
    for (int i = center; i >= l; i--)
    {
        sum = sum + v[i];
        if (sum < left_sum)
          left_sum = sum;
    }

    // Elements to the right of centre
    sum = 0;
    int right_sum = INT_MAX;
    for (int i = center+1; i <= h; i++)
    {
        sum = sum + v[i];
        if (sum < right_sum)
          right_sum = sum;
    }

    // Return de los elementos que están tanto a la izquierda como a la derecha
    return left_sum + right_sum;
}

// Minimum sum sub-vector size m, size v is h-l
int subvectorMinDyV(int v[], int l, int h, int m){
   // Base Case 1
   if ((h-l) <= m) {
       int sum = 0;
       for(int i=0; i<m; i++)
        sum += v[i];
       return sum;
  // Base Case 2
}else if(m*2-1 <= (h-l)){
       int sum=0;
       int sumMin = INT_MAX;
       for(int i=0; i<(l+h)-m;i++){
           sum=0;
           for(int j=i; j<m; j++)
            sum += v[j];

           if(sum < sumMin)
            sumMin = sum;
       }
       return sumMin;
   }


   int center = (l + h)/2;
   /* Possible cases
      a) minimum sum sub-vector is on the left
      b) minimum sum sub-vector is on the right
      c) minimum sum sub-vector is a in the middle */
   return min(subvectorMinDyV(v, l, center, m),
              subvectorMinDyV(v, center+1, h, m),
              minSumCenter(v, l, center, h));
}

int main(){
   int v[] = {6,10,4,2,14,1};
   int n = sizeof(v)/sizeof(v[0]);
   int sumMin = subvectorMinDyV(v, 0, n-1, 3);
   cout << "The minimum amount with DyV is: " << sumMin << endl;

   return 0;
}

非常感谢。

Answer 1

如果你观察你的例子，你就会发现数组是如何分区的。

for n = 6, m = 3

v = 6|10|4|2|14|1
    ---------------
p = 0|1 |2|3|4 |5

g1: 0 1 2
g2: 1 2 3 (1 2 sum already calculated)
g3: 2 3 4 (2 3 sum already calculated)
g4: 3 4 5 (3 4 sum already calculated)

当你收集到m个元素后从左到右，你需要减去c-mth position element. wherec`是当前位置

    void subvectorMin(int* v, int n, int m, int p, int sum){

    if (p >= n) {
    return sum;
    }
int tmp = sum - v[p-m]+ v[p];
    return Min(sum, Min(tmp, subvector(v, n, m, p+1, tmp)));
    }

main() {
for (i = 0; i < m; i++) 
sum += v[i];
    subvectorMin(v, n, m, m,sum);

Answer 2

我不确定您所说的 divide-and-conquer 到底是什么意思。正如其他人所指出的，滑动 window 方法是 O(n)。（你不能做得更好，因为你需要至少查看每个元素一次。）

您的解决方案很接近，只是您在不必要地重新计算总和。这应该可以完成工作

void subvectorMin(int* v, int n, int m)
{
  if (n < m)
  {            
    std::cout << "Cannot calculate sub-vector m. (m<n)";
    return; // return early
  }

  // compute the sum of first m elements
  int sum = 0;  
  for(int i = 0; i < m; ++i) 
    sum += v[i];

  // assume answer is at position 0
  int pos = 0;
  int min_sum = sum;

  // check if there is a minimum sum somewhere else
  for(int i = m; i < n; ++i)
  {
    sum = sum + v[i] - v[i - m]; // THIS is the sliding window that 
                                 // avoids the sum being recomputed

    // if smaller sum is found, update the position
    if(sum < min_sum)
    { 
        min_sum = sum; 
        pos = i - m + 1;
    }
  }    

  std::cout << "The minimum component sum is: " << min_sum
            << " , subvector: {";
  for(int i = pos; i < pos + m; ++i)
      std::cout << " " << v[i];
  std::cout << " }" <<std::endl;
}

使用分而治之技术的最小子向量大小 k

Minimum sub-vector size k with the divide and conquer technique

c++

algorithm

recursion

divide-and-conquer