前端之家

  1. 首页
  2. 问答

采用分治法的最小子向量大小k

• 问答

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

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

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

我需要通过蛮力（下面将介绍滑动窗口）以及分而治之的技术来分析这个问题。然后，我将撰写一份比较报告，并解释说使用滑动窗口可以更好地工作。本文适用于某大学的算法比较项目。但是我需要使用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 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,minSumCenter(v,h));
}

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

   return 0;
}

非常感谢您。

ooole 回答：采用分治法的最小子向量大小k

如果您观察您的示例，那么您将发现数组如何分区。

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-m th position element. where c`是当前位置

    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,sum);
,

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

您所拥有的解决方案已经接近，除了您不必要地重新计算总和。这应该做的

void subvectorMin(int* v,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;
}
algorithmc++divide-and-conquerrecursion
本文链接：https://www.f2er.com/2487330.html

大家都在问