//VERSIONE CON DISPOSIZIONI RIPETUTE

#include <stdio.h>
#include <stdlib.h>

void calcolaResto(int n, int *val, int *disp, int r);
void calcolaRestoR(int pos, int n, int *val, int *dispR, int *sol, int r, int *num, int *best);
int check(int *sol, int n, int *val, int r, int *num);
int numeroMonete(int *sol, int n);
int main()
{
    int n = 3,r;
    int val[3] = {1,10,25};
    int disp[3] = {10,3,2};
    r = 30;

    calcolaResto(n, val, disp, r);
    return 0;
}

void calcolaResto(int n, int *val, int *disp, int r){
    int i=10000, j , k, num;
    int a;
    int *sol, *dispR;
    sol = calloc(n,sizeof(int));
    dispR = malloc(n*sizeof(int));
    for(j=0; j<n; j++)
        dispR[j] = disp[j];
    calcolaRestoR(0,n,val,dispR,sol,r,&num,&i);


    printf("Numero monete: %d", i);
    return;
}

void calcolaRestoR(int pos, int n, int *val, int *dispR, int *sol, int r, int *num, int* best)
{
    int i, ris;
    if(pos >= n){
        if(check(sol, n, val, r, num)){
            if((*num) < (*best))
                *best = *num;
        }
        return;
    }
    for(i = 0; i <= dispR[pos]; i++){
        sol[pos] = i;
        calcolaRestoR(pos+1, n, val, dispR, sol, r, num, best);
    }
    return;
}
int check(int *sol, int n, int *val, int r, int *num){
    int i, conta, ris;
    ris = 0;
    for(i = 0; i < n; i++){
       ris = ris + sol[i]*val[i];
    }

    if(ris == r){
        (*num) = numeroMonete(sol ,n);
        return 1;
    }
    return 0;
}
int numeroMonete(int *sol, int n){
    int ris, i;
    ris = 0;
    for(i = 0; i < n; i++){
        ris += sol[i];
    }
    return ris;
}