Bank Draft Algorithm in C using recursion

Question

I am having doubts about a bank withdrawal algorithm in C. First of all it is better to pass the statement:

Atms in banks are a great invention, but sometimes we need change and the machine delivers R$100 bills. Other times, we want to withdraw a slightly higher value and for safety reasons we would like to receive everything in bills of $ 100,00, but the machine delivers a lot of notes of $ 20,00. The Smart Bank is trying to minimize this problem by giving customers the possibility to choose the value of the banknotes at the time of withdrawal. For this, they need your help to know, given the S value of the withdrawal and how many banknotes of each value the machine has, how many different ways there are to deliver the S value. The bank provides notes of 2, 5, 10, 20, 50 and 100. For example, if S = 22 and the number of notes of each value is N2=5, N5=4, N10=3, N20 = 10, N50 = 0 and N100=10, then there are 4 distinct ways of the machine to deliver the serve value: 20+2, 10+10+2, 10+5+5+2 and 5+5+5+2.

Entree

The first line of the entry contains an integer S, the value of the serve. The second line contains six integers N2, N5, N10, N20, N50 and N100 respectively, the number of banknotes of values 2,5,10,20,50 and 100, available on the machine.

Exit

Your program must print an integer, number of distinct forms of the machine deliver the serve.

I just don’t know how to count how many possibilities, even more that there are many ways. So far this is what I have been able to implement in my code (The Forms function is obviously not implemented at all):

    #include <stdio.h>

typedef struct{
  int q;
  int v;
}din;

int start(din n[],int t,int i){
  if(t>=n[i].v) return i;
  else return start(n,t,i-1);
}

int forms(din n[6],int t,int i){
  int x,k=t,c=0;
  if(n[x].q==0) return forms(n,t,i-1);
  else{
    if(k==0){
      c++;
    }
    else{ 
    }
  } 
}

int main(void){
  int t,x;
  din n[6];
  scanf("%d",&t);
  for(x=0;x<6;x++) scanf("%d",&n[x].q);
  for(x=0;x<6;x++){
    if(x==0) n[x].v=2;
    else if(x==1) n[x].v=5;
    else if(x==2) n[x].v=10;
    else if(x==3) n[x].v=20;
    else if(x==4) n[x].v=50;
    else if(x==5) n[x].v=100;
  }
  printf("%d\n",forms(n,t,start(n,t,5));
  return 0;
 } 

Answer 1

This problem is known in English as "Coin change problem" and if there is interest just take a quick search in Google you can understand how all possibilities are calculated.

But the problem you presented, in particular, has an interesting particularity: the amount of notes is limited. In most of the solutions you will find on the internet, you work with an infinite amount of banknotes (or coins)

Well, I made some changes to your code and replaced the functions start(args) and forms(args) by a single function called count(args). Then I tested with the case you presented and a few others and apparently is working. The solution follows below:

#include <stdio.h>

typedef struct{
   int q;
   int v;
}din;

int count(din notas[], int indice, int saque){

   if(saque == 0) {return 1;}

   if(saque < 0){return 0;}

   if(indice < 0){return 0;}

   int esq, dir;

   if (notas[indice].q <= 0){
      esq = 0;

   } else {

      /*Para se controlar o número de notas, subtrai-se antes de chamar a função e,
      com o retorno da função, restitui-se o valor ao estado anterior*/
      notas[indice].q--;
      esq = count(notas, indice, saque - notas[indice].v);
      notas[indice].q++;
   }
   dir = count(notas, indice - 1, saque);
   return esq + dir;
}

int main(void){
  int t,x;
  din n[6];
  scanf("%d",&t);
  for(x=0;x<6;x++) scanf("%d",&n[x].q);
  for(x=0;x<6;x++){
    if(x==0) n[x].v=2;
    else if(x==1) n[x].v=5;
    else if(x==2) n[x].v=10;
    else if(x==3) n[x].v=20;
    else if(x==4) n[x].v=50;
    else if(x==5) n[x].v=100;
  }
  printf("%d\n",count(n, 5, t));
  return 0;
}