10/06/18 08:20:17
#include <stdio.h>
int mincoin(int num, int n, int idx, int *coins, int maxidx);
int main(){
int coins[] = {1,5,8,10,15};
int num=33;
int n = mincoin(num, 0, 0, coins, sizeof(coins)/sizeof(coins[0]));
printf("%d", n);
return 0;
}
int mincoin(int num, int n, int idx, int *coins, int maxidx){
int i, min, res, rest;
if(num == 0){
return n;
}
min = 10000000;
for(i = idx;i < maxidx;i++){
rest = num-coins[i];
if(rest < 0) break;
res = mincoin(rest, n+1, i, coins, maxidx);
if(res < min){
min = res;
}
}
return min;
}