# include
# include
int Coins(int n, int * faces, int len);
void Printfaces(int n, int * denomination, int length, int* dp);
int main(void){
int n, len;
printf("Please enter the total number of coins:");
scanf("%d", &n);
printf("Please enter the type and number of coins:");
scanf("%d", &len);
printf("Please enter coin denomination:");
//硬币的各面值数组
int * faces = (int*)malloc(sizeof(int)*len);
for(int i = 0; i < len; i++){
scanf("%d", &faces[i]);
}
printf("The number of coins required is %dn", Coins(n, faces, len));
system("pause");
return 0;
}
int Coins(int n, int * faces, int len){
if(n < 1 || faces == NULL || len == 0)
return -1;
//凑够硬币最少需要的硬币个数
int * dp = (int*)calloc((n+1), sizeof(int));
//凑够硬币最后一枚选择的硬币面值
int * denomination = (int*)malloc(sizeof(int)*(n+1));
for(int i = 1; i < n + 1; i++){
int min = INT_MAX;
for(int j = 0; j < len; j++){
if(i < faces[j]) continue;
if(dp[i - faces[j]] < 0 || dp[i - faces[j]] >= min) continue;
min = dp[i - faces[j]];
denomination[i] = faces[j];
}
if(min == INT_MAX){
dp[i] = -1;
denomination[i] = 0;
}
else
{
dp[i] = min + 1;
}
Printfaces(i, denomination, n, dp);
}
return dp[n];
}
void Printfaces(int n, int * denomination, int length, int* dp){
printf("dp[%d]= %d ", n, dp[n]);
printf("denomination =");
while(n > 0)
{
if(denomination[n] == 0){
printf(" Can't scrape together coins！");
break;
}
printf(" %d", denomination[n]);
//denomination[n]凑够n硬币最后一枚选择的硬币面值， n-denomination[n] 剩下要凑的硬币面值
n -= denomination[n];
}
printf("n");
}
