Find Minimum number of coins required to make a given change

Viewed 131

I have seen many answers related to this question but none that solves my problem. I know how to find the change but I want to know how to figure out the number of coins of each individual denomination required to come to that minimum. for example I have the following code in which target is the target amount, coins[] is the coin denominations given, len is the length of coins[]. qty[] is an empty array that I need. to fill with the number of coins in each denomination that we used to get to the result.

    #include <stdio.h>

    int make_change(const int coins[], int len, int target, int qty[]) {
    assert(0 <= target && target <= COINS_MAX_TARGET);
    assert(0 < len);
    // table[i] will be storing the minimum number of coins
    // required for i value.  So table[V] will have result
    int table[4096];

    // Base case (If given value V is 0)
    table[0] = 0;

    // Initialize all table values as Infinite
    for (int i=1; i<=target; i++) {
        table[i] = 4095;
    }

    // Compute minimum coins required for all
    // values from 1 to V
    for (int i=1; i <= target; i++) {
        // Go through all coins smaller than i
        for (int j = 0; j < len; j++)  {
            if (coins[j] <= i) {
                int sub_res = table[i-coins[j]];
                if (sub_res != 4095 && sub_res + 1 < table[i]) {
                    table[i] = sub_res + 1;
                }
            }
        }
    }    

    for(int i = 0; i < len; i++) {
        for(int j = i; i < len; i++) {
            int temp_target = target - coins[i];
            
    if(table[target]==4095) 
        return -1;

    return table[target];
}
0 Answers
Related