/*
Please enter the total number of coins:23
Please enter the type and number of coins:3
Please enter coin denomination:2 5 10
dp[1]= -1 denomination = Can't scrape together coins！
dp[2]= 1 denomination = 2
dp[3]= -1 denomination = Can't scrape together coins！
dp[4]= 2 denomination = 2 2
dp[5]= 1 denomination = 5
dp[6]= 3 denomination = 2 2 2
dp[7]= 2 denomination = 2 5
dp[8]= 4 denomination = 2 2 2 2
dp[9]= 3 denomination = 2 2 5
dp[10]= 1 denomination = 10
dp[11]= 4 denomination = 2 2 2 5
dp[12]= 2 denomination = 2 10
dp[13]= 5 denomination = 2 2 2 2 5
dp[14]= 3 denomination = 2 2 10
dp[15]= 2 denomination = 5 10
dp[16]= 4 denomination = 2 2 2 10
dp[17]= 3 denomination = 2 5 10
dp[18]= 5 denomination = 2 2 2 2 10
dp[19]= 4 denomination = 2 2 5 10
dp[20]= 2 denomination = 10 10
dp[21]= 5 denomination = 2 2 2 5 10
dp[22]= 3 denomination = 2 10 10
dp[23]= 6 denomination = 2 2 2 2 5 10
The number of coins required is 6
请按任意键继续. . .
*/
# include<stdio.h>
# include<stdlib.h>
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 %d\n", 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");
}
