Question

Write a progran1 that asks the user to enter a U.S. dollar amount and tben shows how to pay that amount using the smallest number of $20, $IO. $5, and $1 biJ ls?

Answer 1

for this problem the greedy strategy is optimal,

"pay as much with the highest denomination available"

for example $56 are paid with 2 $20 , 1 $10 and 1 $5 and 1 $1 bill.

the c code is:

#include <stdio.h>

int main() {
    int twenty=0;
    int tens=0;
    int fives=0;
    int ones=0;
    int amount;
    printf("Enter an integer amount:\n");
    scanf("%d",&amount);
    while(amount>=20){
        amount=amount-20;
        twenty++;
    }
     while(amount>=10){
        amount=amount-10;
        tens++;
    }
     while(amount>=5){
        amount=amount-5;
        fives++;
    }
     while(amount>0){
        amount=amount-1;
        ones++;
    }
    printf("Number of bills required is:%d ",twenty+tens+fives+ones);
    return 0;
}