c++ - 采用分治法的最小子 vector 大小k

Question

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

您有一个大小为n的 vector ，您想找到一个大小为m的子 vector ，并且其元素之和为最小

一个如何工作的示例是:
see example of operation
其中最小子 vector 为:{1,3,1}，总和为5

我需要通过蛮力(滑动窗口在下面说明)以及分而治之的技术来分析这个问题。然后，我将撰写一份比较报告，并解释说使用滑动窗口可以更好地工作。本文是针对某大学的算法比较项目。但是我需要使用D＆C显式构建它。

我做了如下操作，但是在基本情况和返回最小和子 vector 时遇到问题。

// 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

我不确定divide-and-conquer是什么意思。正如其他人指出的，滑动窗口方法是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;
}