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