Maximize count of array elements required to obtain given sum

0 0 6 minutes read

Given an integer V and an array arr[] consisting of N integers, the task is to find the maximum number of array elements that can be selected from array arr[] to obtain the sum V. Each array element can be chosen any number of times. If the sum cannot be obtained, print -1.

Examples:

Input: arr[] = {25, 10, 5}, V = 30
Output: 6
Explanation:
To obtain sum 30, select arr[2] (= 5), 6 times.
Therefore, the count is 6.

Input: arr[] = {9, 6, 4, 3}, V = 11
Output: 3
Explanation:
To obtain sum 11, possible combinations is : 4,4,3
Therefore, the count is 3

Naive Approach: The simplest approach is to recursively find the maximum number of array elements to generate the sum V using array elements from indices 0 to j before finding the maximum number of elements required to generate V using elements from indices 0 to i where j < i < N. After completing the above steps, print the count of array elements required to obtain the given sum V.

Time Complexity: O(V^N)
Auxiliary Space: O(N)

Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming. Follow the below steps to solve the problem:

Initialize an array table[] of size V + 1 where table[i] will store the optimal solution to obtain sum i.
Initialize table[] with -1 and table[0] with 0 as 0 array elements are required to obtain the value 0.
For each value from i = 0 to V, calculate the maximum number of elements from the array required by the following DP transition:

table[i] = Max(table[i – arr[j]], table[i]), Where table[i-arr[j]]!=-1
where 1 ? i ? V and 0 ? j ? N

After completing the above steps, print the value of the table[V] which is the required answer.

Below is the implementation of the above approach:

C++14

// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that count the maximum
// number of elements to obtain sum V
int maxCount(vector<int> arr, int m, int V)
{
 
    // Stores the maximum number of
    // elements required to obtain V
    vector<int> table(V + 1);
 
    // Base Case
    table[0] = 0;
 
    // Initialize all table values
    // as Infinite
    for (int i = 1; i <= V; i++)
        table[i] = -1;
 
    // Find the max arr required
    // for all values from 1 to V
    for (int i = 1; i <= V; i++) {
 
        // Go through all arr
        // smaller than i
        for (int j = 0; j < m; j++) {
 
            // If current coin value
            // is less than i
            if (arr[j] <= i) {
                int sub_res = table[i - arr[j]];
 
                // Update table[i]
                if (sub_res != -1 && sub_res + 1 > table[i])
                    table[i] = sub_res + 1;
            }
        }
    }
 
    // Return the final count
    return table[V];
}
 
// Driver Code
int main()
{
 
    // Given array
    vector<int> arr = { 25, 10, 5 };
    int m = arr.size();
 
    // Given sum V
    int V = 30;
 
    // Function call
    cout << (maxCount(arr, m, V));
 
    return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
 
    // Function that count the maximum
    // number of elements to obtain sum V
    static int maxCount(int arr[], int m, int V)
    {
        // Stores the maximum number of
        // elements required to obtain V
        int table[] = new int[V + 1];
 
        // Base Case
        table[0] = 0;
 
        // Initialize all table values
        // as Infinite
        for (int i = 1; i <= V; i++)
            table[i] = -1;
 
        // Find the max arr required
        // for all values from 1 to V
        for (int i = 1; i <= V; i++) {
 
            // Go through all arr
            // smaller than i
            for (int j = 0; j < m; j++) {
 
                // If current coin value
                // is less than i
                if (arr[j] <= i) {
 
                    int sub_res = table[i - arr[j]];
 
                    // Update table[i]
                    if (sub_res != -1
                        && sub_res + 1 > table[i])
                        table[i] = sub_res + 1;
                }
            }
        }
 
        // Return the final count
        return table[V];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array
        int arr[] = { 25, 10, 5 };
        int m = arr.length;
 
        // Given sum V
        int V = 30;
 
        // Function Call
        System.out.println(maxCount(arr, m, V));
    }
}

Python3

# Python program for the
# above approach
 
# Function that count
# the maximum number of
# elements to obtain sum V
def maxCount(arr, m, V):
    '''
    You can assume array elements as domination 
    which are provided to you in infinite quantity 
    just like in coin change problem.
    I made a small change in logic on coin change 
    problem (minimum number of coins required).
    There we use to take min(table[i-arr[j]]+1,table[i]),
    here min is changed with max function.
    Dry run:
    assume : target = 10, arr = [2,3,5]
 
    table   0  1  2  3  4  5  6  7  8  9  10
            0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
 
    taking first domination = 2
 
    table    0  1  2  3  4  5  6  7  8  9  10
             0 -1  1 -1  2 -1  3 -1  4 -1  5
 
    taking second domination = 3
 
    table    0  1  2  3  4  5  6  7  8  9  10  
             0 -1  1  1  2 -1  3 -1  4  3  5   
    here for i = 6 we have max(table[i-dom]+1,table[i])         
    hence 
    => max(table[6-3]+1,table[6]) 
    => max(2,3) => 3
 
    taking third domination = 5
 
    table    0  1  2  3  4  5  6  7  8  9  10  
             0 -1  1  1  2  1  3 -1  4  3  5  
 
    Hence total 5 coins are required (2,2,2,2,2)
    '''
    # Stores the maximum
    # number of elements
    # required to obtain V
    table = [0 for i in range(V+1)]
 
    # Base Case
    table[0] = 0
 
    # Initialize all table
    # values as Infinite
    for i in range(1, V + 1, 1):
        table[i] = -1
 
        # Find the max arr required
        # for all values from 1 to V
        for i in range(1, V + 1, 1):
 
            # Go through all arr
            # smaller than i
            for j in range(0, m, 1):
 
                # If current coin value
                # is less than i
                if (arr[j] <= i):
                    sub_res = table[i - arr[j]]
 
                    # Update table[i]
                    if (sub_res != -1 and
                        sub_res + 1 > table[i]):
                        table[i] = sub_res + 1
 
    # Return the final count
    return table[V]
 
 
# Driver Code
if __name__ == '__main__':
 
    # Given array
    arr = [25, 10, 5]
    m = len(arr)
 
    # Given sum V
    V = 30
 
    # Function Call
    print(f'Maximum number of array elements required : 
                                 {maxCount(arr, m, V)}')
 
# This code is contributed by Aaryaman Sharma

C#

// C# program for the 
// above approach
using System;
class GFG{
     
// Function that count the 
// maximum number of elements 
// to obtain sum V
static int maxCount(int[] arr, 
                    int m, int V)
{
  // Stores the maximum number of
  // elements required to obtain V
  int[] table = new int[V + 1];
 
  // Base Case
  table[0] = 0;
 
  // Initialize all table 
  // values as Infinite
  for (int i = 1; i <= V; i++)
    table[i] = -1;
 
  // Find the max arr required
  // for all values from 1 to V
  for (int i = 1; i <= V; i++) 
  {
    // Go through all arr
    // smaller than i
    for (int j = 0; j < m; j++) 
    {
      // If current coin value
      // is less than i
      if (arr[j] <= i) 
      {
        int sub_res = table[i - arr[j]];
 
        // Update table[i]
        if (sub_res != -1 && 
            sub_res + 1 > table[i])
          table[i] = sub_res + 1;
      }
    }
  }
 
  // Return the final count
  return table[V];
}
     
// Driver code
static void Main() 
{
  // Given array
  int[] arr = {25, 10, 5};
  int m = arr.Length;
 
  // Given sum V
  int V = 30;
 
  // Function Call
  Console.WriteLine(maxCount(arr, 
                             m, V));
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// Javascript program for the above approach
 
    // Function that count the maximum
    // number of elements to obtain sum V
    function maxCount(arr, m, V)
    {
        // Stores the maximum number of
        // elements required to obtain V
        let table = [];
  
        // Base Case
        table[0] = 0;
  
        // Initialize all table values
        // as Infinite
        for (let i = 1; i <= V; i++)
            table[i] = -1;
  
        // Find the max arr required
        // for all values from 1 to V
        for (let i = 1; i <= V; i++) {
  
            // Go through all arr
            // smaller than i
            for (let j = 0; j < m; j++) {
  
                // If current coin value
                // is less than i
                if (arr[j] <= i) {
  
                    let sub_res = table[i - arr[j]];
  
                    // Update table[i]
                    if (sub_res != -1
                        && sub_res + 1 > table[i])
                        table[i] = sub_res + 1;
                }
            }
        }
  
        // Return the final count
        return table[V];
    }
 
 
// Driver Code
 
        // Given array
        let arr = [ 25, 10, 5 ];
        let m = arr.length;
  
        // Given sum V
        let V = 30;
  
        // Function Call
        document.write(maxCount(arr, m, V));
 
</script>

Output

Time Complexity: O(N * V)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!