Минимальный размер субвектора k с техникой «разделяй и властвуй»

Question

Доброе утро, у меня есть проблемы, которые нужно решить:

У вас есть вектор размера n, вы хотите найти подвектор размера m и сумма его элементов минимальна

Пример того, как это работает: см. Пример операции , где минимальный субвектор: {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

Я не уверен, что именно вы подразумеваете под 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;
}

Answer 2

Если вы посмотрите на ваш пример, то вы узнаете, как массив разбивается.

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)

Когда вы go слева направо после сбора 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, n, m, m,sum);