基于分治技术的最小子向量尺寸k

Question

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

我做了如下，但我有基本情况和返回最小和子向量的问题。

// 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-m第1个位置元素。其中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, n, m, m,sum);