Answers for "minimum coin change problem"

coin change problem minimum number of coins dynamic programming

class Main
{
    // Function to find the minimum number of coins required
    // to get total of N from set S
    public static int findMinCoins(int[] S, int N)
    {
        // T[i] stores minimum number of coins needed to get total of i
        int[] T = new int[N + 1];
 
        for (int i = 1; i <= N; i++)
        {
            // initialize minimum number of coins needed to infinity
            T[i] = Integer.MAX_VALUE;
            int res = Integer.MAX_VALUE;
 
            // do for each coin
            for (int c: S)
            {
                // check if index doesn't become negative by including
                // current coin c
                if (i - c >= 0) {
                    res = T[i - c];
                }
 
                // if total can be reached by including current coin c,
                // update minimum number of coins needed T[i]
                if (res != Integer.MAX_VALUE) {
                    T[i] = Integer.min(T[i], res + 1);
                }
            }
        }
 
        // T[N] stores the minimum number of coins needed to get total of N
        return T[N];
    }
 
    public static void main(String[] args)
    {
        // n coins of given denominations
        int[] S = { 1, 2, 3, 4 };
 
        // Total Change required
        int N = 15;
 
        int coins = findMinCoins(S, N);
        if (coins != Integer.MAX_VALUE) {
            System.out.print("Minimum number of coins required to get desired change is "
                + coins);
        }
    }
}

minimum coin change problem

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
    return(a>b);
}
int main()
{
    int n;
    cin>>n;
    int coin_type[n];
    for(int i=0;i<n;i++)
    {
        cin>>coin_type[i];
    }
    sort(coin_type,coin_type+n,cmp);
    int amount;
    cin>>amount;
    int i=0;
    int count=0;
    while(amount>0)
    {
        if(coin_type[i]<=amount)
        {
            count++;
            amount=amount-coin_type[i];
        }
        else
        {
            i++;
        }
    }
    cout<<count<<endl;
    return 0;
}