Description

Suppose that you have a lot of coins and bills of different values, but the numbers of them are limited. 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 10 coins in $1, 10 coins in $5, and 10 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 10 coins in $1, 10 coins in $5, 10 bills in $10 and zero bills in $50. To get the change for $57, we need 5 bills of $10, 1 coins of $5, and 2 coins of $1.

Note that you can always find at least one way to get the change.

The following is an excerpt of incomplete code:

#include 
#define MAXNV 5

int DONE = 0;
int values[MAXNV];
int limits[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
  
Input
  
The input contains three lines. The first line contains an integer N (0The third line contains N integers indicating the limited numbers of the coins and bills. The final line contains the amount of money for change.
  
Output
  
The result can be displayed by calling the function show()

Only the best way for change should be displayed.
  
Sample Input  Download
  

    4
50 10 5 1
0 10 10 10
57
  
  
Sample Output  Download
  

    (0,5,1,2)
 
  
  
  
  
  
Tags
    

      
        
      
    
    
      

        
        

          
          
	    
	      Add Tag
	    
          
        
      
    
  

  

  

  

  

    Discuss