Description

Suppose that you have a lot of coins and bills of different values. Given an amount of money, you need to find the best way to get the change. By ‘best’, we mean that we the total number of coins should be as small as possible. For example, assume that we have coins in $1 and $5, and bills in $10. To get the change for $17, we need 2 coins of $1, 1 coin of $5, and 1 bill of $10. Another example: assume that we have coins in $1 and $5, and bills in $10 and $50. To get the change for $57, we need 1 bill of $50, 1 coin of $5, and 2 coins of $1.

The following is an excerpt of incomplete code:

#include <stdio.h>
#define MAXNV 5
int DONE = 0;
int values[MAXNV];
int numbers[MAXNV];
void show(int nv);
void change(int amount, int cur, int nv);
int main(void)
{
    int nv, i;
    int money;
    scanf("%d", &nv);
    for (i=0; i<nv; i++) {
        scanf("%d", &values[i]);
    }
    scanf("%d", &money);
    change(money, 0, nv);
    return 0;
}
void show(int nv)
{
    int i;
    printf("(%d", numbers[0]);
    for (i=1; i<nv; i++) {
        printf(",%d", numbers[i]);
    }
    printf(")\n");
}
void change(int amount, int cur, int nv)
{
/* your code */
}

Input

The input contains three lines. The first line contains an integer N (0

Output

The result can be displayed by calling the function show()
Only the best way for change should be displayed.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss