CODEWITHSUNDEEP
c++algorithmdynamic-programming
user2560730
user2560730

Reputation: 345

Find the minimum sum of 'P' elements in an array of N elements such that no more than 'k' consecutive elements are selected together

Suppose the array is 1 2 3 4 5 Here N = 5 and we have to select 3 elements and we cannot select more than 2 consecutive elements, so P = 3 and k = 2. So the output here will be 1 + 2 + 4 = 7.

I came up with a recursive solution, but it has an exponential time complexity. Here is the code.

#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;

}

Also, if supposedly P elements cannot be selected following the constraint, then we return INT_MAX.

I was asked this question in an interview. After proposing this solution, the interviewer was expecting something faster. Maybe, a DP approach towards the problem. Can someone propose a DP algorithm if there exists one, or a faster algorithm.

I have tried various tests cases and got correct answers. If you find some test cases that are giving incorrect response, please point that out too.

Upvotes: 2

Views: 2730

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55589

Below is a Java Dynamic Programming algorithm.
(the C++ version should look very similar)

It basically works as follows:

  • Have a 3D array of [pos][consecutive length][length]
    Here length index = actual length - 1), so [0] would be length 1, similarly for consecutive length. This was done since there's no point to having length 0 anywhere.
  • At every position:
    • If at length 0 and consecutive length 0, just use the value at pos.
    • Otherwise, if consecutive length 0, look around for the minimum in all the previous positions (except pos - 1) with length - 1 and use that plus the value at pos.
    • For everything else, if pos > 0 && consecutive length > 0 && length > 0,
      use [pos-1][consecutive length-1][length-1] plus the value at pos.
      If one of those are 0, initialize it to an invalid value.

Initially it felt like one only needs 2 dimensions for this problem, however, as soon as I tried to figure it out, I realized I needed a 3rd.

Code:

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

Here we get 7 as output, as expected.

Running time: O(N2k + NPk)

Upvotes: 3

Related Questions