CODEWITHSUNDEEP
javaalgorithmdynamic
Niammi
Niammi

Reputation: 76

Minimum sum of n numbers with k spaces in between of a given array of size N

Using dynamic programming I have to find an efficent algorithm to solve the following problem:

As input we receive an array of random numbers of size N, an int k that is the minimum distance between chosen numbers and an int n that is the total number of numbers we have to pick. The goal of the problem is to find out what is the minimum possible sum of the n chosen numbers. I can't figure out how to aproach this problem.

As an example if we have the following array:

arr = [5, 5, 3, 3, 2, 2, 3, 3, 5, 5, 5, 5, 5, 3, 2, 5]
N = 16
k = 4
n = 3

the output would be 8 (3+3+2), by selecting the numbers at index 2, 7 and 14.

Upvotes: 0

Views: 520

Answers (1)

KauziJoshi
KauziJoshi

Reputation: 63

I have coded the solution in c++, The code is readable for the most part but if you have any ambiguity in understanding it, comment below. 

#include<iostream>
#include<vector>
using namespace std;
int number_of_elements_to_be_picked, number_of_elements, k;
int main(){
      cin >> number_of_elements >> k >> number_of_elements_to_be_picked;
      vector<int> a(number_of_elements);
      vector<vector<int> > store(number_of_elements, vector<int> (number_of_elements_to_be_picked+1));
      for(int i = 0; i < number_of_elements; i++){
              cin >> a[i];
              store[i][1] = a[i];
      }
      for(int i = 0; i < number_of_elements; i++){
              for(int j = 2; j <= number_of_elements_to_be_picked; j++){
                      if(i == k*(j-1))
                              store[i][j] = store[i-k][j-1]+a[i];
                      else if(i > k*(j-1))
                              store[i][j] = min(store[i-k][j-1]+a[i], store[i-1][j]);
              }
      }
      cout << store[number_of_elements-1][number_of_elements_to_be_picked] << "\n";
      return 0;
}

edit: I had incorrectly named variables, by Author's notation :-
N = number_of_elements, n = number_of_elements_to_be_picked, k = k

Upvotes: 2

Related Questions