need an explanation for this answer? contact us directly to get an explanation for this answer

1) Recursive solution

We will start the solution with initially sum = V cents and at each iteration find the minimum coins required by dividing the problem into subproblems where we take {C1, C2, ..., CN} coin and decrease the sum V.

By C[i] (based on the coin we took). Whenever V becomes 0, this means we have a possible or otherwise there is no solution and we return -1;

Solution: To find the optimal answer, we return the minimum of all answers for which N became 0.

If V == 0, then 0 coins required.

We calculate the total required number of coins using the following function:

    int mincoins(coins array[], size of the array, required sum);

So, initially the function call would be:

    int mincoins(C,N,V);

Where C is the coins array, N is the size of the coin array and V is the required sum.

Now our idea is the get the minimum number of coins from the given array
and if the sum that we want to get if not possible from the given set of coins we will return -1.

So, let's see the function definition:

Function:

    Mincoins(int coins[],int N,int V):
	    if V==0,then 0 coins are required
	    if V>0:
	        mincoins{V,coins[0...N-1]}=min{1+mincoins{N-coins[i],coins[0...N-1]}}
            Where, i varies from 0 to N-1 and coins<=N
    End Function

Pseudo Code:

    int Mincoins(coins[],N,V):
	    if(V==0)
		    return 0 //base case
	    else{
		    res=INT_MAX //if res=INT_MAX==-1 in the answer
		    for(i=0;i<N;i++){
			    sub;
			    if(coins[i]>=V){ 
				    // recursive call
                    sub=1+mincoins(coins,N,V-coins[i]) 
				    // assigning the min value to res
                    res=min(res,subres) 
			    }
		    }
		    return res//return the result of mincoins.
	    }

The recursive definition consists of the part:

    mincoins{V,coins[0...N-1]}=min{1+mincoins{N-coins[i],coins[0...N-1]}}

This recursive part will generate a recursion tree where we can find many overlapping subproblems, hence we would solve by dynamic programming.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int mincoins(int C[], int N, int V)
{
    if (V == 0)
        return 0;
    int res = INT_MAX;
    for (int i = 0; i < N; i++) {
        int sub;
        if (V >= C[i]) {
            sub = 1 + mincoins(C, N, V - C[i]);
            res = min(res, sub);
        }
    }
    return res;
}

int main()
{
    cout << "Enter number of test cases: ";
    int t;
    cin >> t;
    
    while (t--) {
        int N, V;
        
        cout << "Enter the size of Coins array: ";
        cin >> N;
        
        int C[N];
        cout << "Enter the coins: ";
        for (int i = 0; i < N; i++)
            cin >> C[i];
            
        cout << "Enter V (Required sum): ";
        cin >> V;
        
        int res = INT_MAX;
        res = mincoins(C, N, V);
        if (res == INT_MAX or res < 0) {
            cout << "NOT POSSIBLE: ";
            cout << -1;
        }
        else {
            cout << "Required coins: ";
            cout << res << "\n";
        }
    }
    return 0;
}

Output

Enter number of test cases: 3 
Enter the size of Coins array: 3 
Enter the coins: 5 25 10
Enter V (Required sum): 20 
Required coins: 2 
Enter the size of Coins array: 4 
Enter the coins: 9 5 6 1
Enter V (Required sum): 13 
Required coins: 3 
Enter the size of Coins array: 3 
Enter the coins: 7 6 8  
Enter V (Required sum): 9  
NOT POSSIBLE: -1 

2) Dynamic Programming Approach

Since the same subproblems are called, again and again, this problem has Overlapping Subproblems property.

Like other typical Dynamic Programming (DP) problems, re-computations of the same subproblems can be avoided by constructing a temporary array dp[] and memorizing the computed values in this array.

We will declare a dp[] array of length equal to the sum required+1 since indexing starts from 0, we will use Top-Down DP, use memoization plus recursion approach.

Initially, we will fill the dp[] array with -1 so that during recursion call if the array if not -1 then we don't have to calculate the value we just need to return the dp[value](memoized array), else we will call the function and fill the required value of the array.

2.1) Top Down Approach

pseudo code:

    int mincoins(coins[],dp[],N,m){
	    // where N is the size if coins array and m is the value 
	    // of cents for which we are calculating the number of coins.

	    if(dp[m]!=-1)	//if we have already solved the subproblem
		    return dp[m]	//directly return the memoized value.
	    if(m==0)	//base case
		    return 0

	    res=INT_MAX //initializ the result
	    for(i=0;i<N;i++){
		    if(coins[i]<=m){
			    sub=1+mincoins(coins,dp,m-coins[i])
			    //recursive  call				
			    if(res>sub)
			    res=min(res,sub)	
		    }
	    }
	    dp[m]=res
	    return dp[m]	
    }

 

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int mincoins(int coins[], int N, int dp[], int V)
{
    if (dp[V] != -1)
        return dp[V];
    if (V == 0)
        return 0;
    else {
        int res = 1000000009;
        for (int i = 0; i < N; i++) {
            if (V >= coins[i]) {
                int sub = 1 + mincoins(coins, N, dp, V - coins[i]);
                res = min(res, sub);
            }
        }
        dp[V] = res;
    }
    return dp[V];
}

int main()
{
    int t;
    
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        int N, V;
        
        cout << "Enter size of coins array: ";
        cin >> N;
        
        int coins[N];
        cout << "Enter coins: ";
        for (int i = 0; i < N; i++)
            cin >> coins[i];
            
        cout << "Enter V (required sum): ";
        cin >> V;
        
        int dp[V + 1];
        for (int i = 0; i <= V; i++)
            dp[i] = -1;
        
        dp[0] = 0;
        dp[V] = mincoins(coins, N, dp, V);
        
        if (dp[V] == 1000000009) {
            cout << "Not Possible: ";
            cout << -1 << "\n";
        }
        else {
            cout << "Required coins: ";
            cout << dp[V] << "\n";
        }
    }
    return 0;
}

Output

Enter number of test cases: 3 
Enter size of coins array: 3  
Enter coins: 5 25 10 
Enter V (required sum): 20 
Required coins: 2 
Enter size of coins array: 4  
Enter coins: 9 5 6 1 
Enter V (required sum): 13 
Required coins: 3 
Enter size of coins array: 3  
Enter coins: 7 6 8
Enter V (required sum): 9  
Not Possible: -1 

2.2) Bottom Up Approach

ith state of dp : dp[i] : Minimum number of coins required to sum to i cents.

In this approach, we move from the base case to the desired value of the sum
base dp[0]=0 , where for 0 cents of value we need 0 coins.

Initially, we will fill the dp[] array with INT_MAX and dp[0]=0 as for 0 cents we need 0 coins.

Then we will iterate from 1 cent required sum to V value cents.

we will use the outer loop for sum array and inner loop for coins array.

Pseudo Code:

    int minCoins(int coins[],int dp[],int N, int V)
    {
	    // Initializing all values to infinity i.e. minimum coins to make any
	    // amount of sum is INT_MAX
	    for(i = 0;i<=N;i++)
		    dp[i] = INF

	    // Base case i.e. minimum coins to make sum = 0 cents is 0
	    dp[0] = 0;

	    // Iterating in the outer loop for possible values of sum between 1 to V
	    // Since our final solution for sum = N might depend upon any of these values
	    for(i=1;i<=V;i++){
		    // Inner loop denotes the index of coin array.
		    // For each value of sum, to obtain the optimal solution.
		    for(j = 0;j<N;j++){
			    // i —> sum
			    // j —> next coin index
			    // If we can include this coin in our solution
			    if(coins[j] <= i){
				    // Solution might include the newly included coin.
				    dp[i] = min(dp[i], 1 + dp[i - coins[j]])
			    }
		    }
	    }
	    //for(i = 1;i<=N;i++)
	    return dp[N];
    }

The overall Time complexity of this approach is O(N*V).

 

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        int N, V;

        cout << "Enter size of coins array: ";
        cin >> N;

        int coins[N];
        cout << "Enter coins: ";
        for (int i = 0; i < N; i++)
            cin >> coins[i];

        cout << "Enter V (required sum): ";
        cin >> V;
        
        int dp[V + 1];
        for (int i = 0; i <= V; i++)
            dp[i] = 1000000009;
        
        dp[0] = 0;
        
        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < N; j++) {
                if (i >= coins[j]) {
                    dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
                }
            }
        }
        
        if (dp[V] == 1000000009) {
            cout << "Not Possible: ";
            cout << -1 << "\n";
        }
        else {
            cout << "Required coins: ";
            cout << dp[V] << "\n";
        }
    }
    return 0;
}

Output

 

Enter number of test cases: 3 
Enter size of coins array: 3  
Enter coins: 5 25 10 
Enter V (required sum): 20 
Required coins: 2 
Enter size of coins array: 4  
Enter coins: 9 5 6 1 
Enter V (required sum): 13 
Required coins: 3 
Enter size of coins array: 3  
Enter coins: 7 6 8
Enter V (required sum): 9  
Not Possible: -1  

need an explanation for this answer? contact us directly to get an explanation for this answer