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(VN)
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 Vint 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 Codeint 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 approachimport 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 Vdef 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 Codeif __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 approachusing System;class GFG{ // Function that count the // maximum number of elements // to obtain sum Vstatic 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 codestatic 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
6
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
