Найти минимальную сумму элементов «P» в массиве из N элементов, так что не более чем «k» последовательных элементов выбраны вместе

Question

Предположим, что массив равен 1 2 3 4 5 Здесь N = 5 и нам нужно выбрать 3 элемента, и мы не можем выбрать более 2 последовательных элементов, поэтому P = 3 и k = 2. Таким образом, выход будет 1 + 2 + 4 = 7.

Я придумал рекурсивное решение, но оно имеет экспоненциальную временную сложность. Вот код.

#include<iostream> 

using namespace std; 

void mincost_hoarding (int *arr, int max_size, int P, int k, int iter, int& min_val, int sum_sofar, int orig_k) 
{ 
    if (P == 0) 
    { 
     if (sum_sofar < min_val) 
      min_val = sum_sofar; 
     return; 
    } 

    if (iter == max_size) 
     return; 



    if (k!=0) 
    { 
     mincost_hoarding (arr, max_size, P - 1, k - 1, iter + 1, min_val, sum_sofar + arr[iter], orig_k); 
     mincost_hoarding (arr, max_size, P, orig_k, iter + 1, min_val, sum_sofar, orig_k); 
    } 
    else 
    { 
     mincost_hoarding (arr, max_size, P, orig_k, iter + 1, min_val, sum_sofar, orig_k); 
    } 

} 



int main() 
{ 
    int a[] = {10, 5, 13, 8, 2, 11, 6, 4}; 

    int N = sizeof(a)/sizeof(a[0]); 
    int P = 2; 
    int k = 1; 


    int min_val = INT_MAX; 
    mincost_hoarding (a, N, P, k, 0, min_val, 0, k); 

    cout<<min_val; 

} 

Кроме того, если предположительно элементы P не могут быть выбраны после ограничения, то мы возвращаем INT_MAX.

Мне задали этот вопрос в интервью. Предложив это решение, интервьюер ожидал чего-то более быстрого. Возможно, подход DP к проблеме. Может ли кто-то предложить алгоритм DP, если он существует, или более быстрый алгоритм.

Я пробовал различные тесты и получил правильные ответы. Если вы найдете некоторые тестовые примеры, которые дают неверный ответ, укажите это тоже.

Answer 1

Ниже представлен алгоритм динамического программирования Java.
(C++ версия должна выглядеть очень похоже)

Это в основном работает следующим образом:

• Есть 3D массив [pos][consecutive length][length]
  Здесь length index = actual length - 1), так [0] будет длина 1, аналогично для последовательной длины , Это было сделано, поскольку нет смысла иметь длину 0 в любом месте.
• На каждой позиции:
  • Если при длине 0 и последовательной длиной 0, просто использовать значение по pos.
  • В противном случае, если последовательная длина 0, осмотрите минимум на всех предыдущих позициях (кроме pos - 1) с length - 1 и используйте это значение плюс pos.
  • Для всего остального, если pos > 0 && consecutive length > 0 && length > 0,
    [pos-1][consecutive length-1][length-1] плюс стоимость на pos.
    Если один из них равен 0, инициализируйте его недопустимым значением.

Первоначально казалось, что один только нужно 2 размеры для этой проблемы, однако, как только я попытался выяснить это, я понял, что мне нужен был 3-й.

Код:

int[] arr = {1, 2, 3, 4, 5}; 
    int k = 2, P = 3; 

    int[][][] A = new int[arr.length][P][k]; 

    for (int pos = 0; pos < arr.length; pos++) 
    for (int len = 0; len < P; len++) 
    { 
    int min = 1000000; 
    if (len > 0) 
    { 
     for (int pos2 = 0; pos2 < pos-1; pos2++) 
     for (int con = 0; con < k; con++) 
      min = Math.min(min, A[pos2][len-1][con]); 
     A[pos][len][0] = min + arr[pos]; 
    } 
    else 
     A[pos][0][0] = arr[pos]; 

    for (int con = 1; con < k; con++) 
     if (pos > 0 && len > 0) 
      A[pos][len][con] = A[pos-1][len-1][con-1] + arr[pos]; 
     else 
      A[pos][len][con] = 1000000; 
    } 

    // Determine the minimum sum 
    int min = 100000; 
    for (int pos = 0; pos < arr.length; pos++) 
    for (int con = 0; con < k; con++) 
    min = Math.min(A[pos][P-1][con], min); 
    System.out.println(min); 

Здесь мы получаем 7 в качестве выходного сигнала, как и ожидалось.

Продолжительность:O(N2k + NPk)