Let a set of coins consist of sufficient number of quarters

Let a set of coins consist of sufficient number of quarters, dimes, nickels, and pennies. (a) Describe a greedy algorithm to make change for n cents such that it uses the LEAST number of coins. (b) Prove your algorithm yields an optimal solution. (c) Instead of quarters, dimes, nickels, and pennies, give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. (greedy method)

Answer a). Code for Greedy algorithm to make change.

#include <stdio.h>

int main(void)
{
    int cents;
    int coinvalues[] = {25, 10, 5, 1}; // set of denominations
    int coins = 0;

    printf(\"How much change is owed? \ \");
    scanf(\"%d\", &cents);

    while(cents <= 0);
    int i = 0;
    while(cents > 0)
    {
        if(cents >= coinvalues[i])
        {
            coins += cents / coinvalues[i];
            cents %= coinvalues[i];
            i++;
            if(cents == 0)
            {
                printf(\"This is an optimal solution\ \");
            }
        }
        else
        {
            printf(\"This is not an optimal solution\ \");
            cents = 0;
        }
    }
    printf(\"Total coins = %d\ \", coins);

}

1. First provide set of denominations in array and no. of cents you want to change.

2. If no. of cents greater than 0, then enter the while loop and remains in the loop until cents become zero.

a. If no. of cents greater than or equal to first array element , then calculate coins of that denomination and get remaining cents. Then move to the next denomination. If there are no remaining cents then the solution is optimal.

b. If no. of cents less than array element, then the solution is non-optimal.

b). This algorithm yields an optimal solution for set of denominations (quarters(25), dimes(10), nickels(5), and pennies(1)).

Let No. of cents = 269

coins = 10 quarters + 1 dime + 1 nickels + 4 pennies = 16

c).

For 269 cents

using denominations (25, 10, 5, 3), this does not provide optimal solution.

coins = 25*10 + 10*1 + 5*1 +3*1 = 15 coins + 1 cent remaining