问题描述及代码:
1 /*
2 * Problem:
3 * given you the coins, and the total amount of money to change, find a solution
4 * for this change which minimize the number of coins needed.
5 *
6 * Example:
7 * coins[] = {1, 5, 10, 21, 25};
8 * money = 19;
9 * solution[] = {10, 5, 1, 1, 1, 1};
10 *
11 * Points:
12 * Dynamic Programming
13 * Greey Algorithm here is usually uncorrect
14 */
15 #include<stdio.h>
16 #include<stdlib.h>
17 #include<string.h>
18 #define MAX_COINS 10
19 #define MAX_MONEY 32767
20 #define INF 0x7FFFFFFF
21 int coins_num, coins[MAX_COINS];
22 int total, changes_num[MAX_MONEY], changes[MAX_MONEY];
23
24 int
25 is_continue()
26 {
27 char ch[2];
28 while(1) {
29 printf("Are you gonna continue this game(Y if yes, or N)?\n");
30 scanf("%s", ch);
31 if(ch[0] == 'Y' || ch[0] == 'y')
32 return 1;
33 else if(ch[0] == 'N' || ch[0] == 'n')
34 return 0;
35 }
36 }
37
38 void
39 input()
40 {
41 int i;
42 printf("Enter the number of coins: ");
43 scanf("%d", &coins_num);
44 printf("Enter the amount of coins(ascending order, separated by space): \n");
45 for(i=0; i<coins_num; i++)
46 scanf("%d", coins+i);
47 printf("Enter the amount of money to change: ");
48 scanf("%d", &total);
49 }
50
51 void
52 output()
53 {
54 int i, tmp;
55 printf("Solution: \n");
56 printf("Minimum number of coins needed: %d\n", changes_num[total]);
57 printf("Coins: \n");
58 tmp = total;
59 while(tmp > 0) {
60 printf("%d ", changes[tmp]);
61 tmp -= changes[tmp];
62 }
63 printf("\n");
64 }
65
66 /*
67 * Dynamic Programming: f(m) = min (f[m-coins[i] + 1)
68 * O(N*K), N is the number of coins, K is the total amount of money to change
69 */
70 void
71 solve()
72 {
73 int i, j, k, min;
74 changes_num[0] = 0;
75 for(i=1; i<=total; i++) { /* Money: from '1' to 'total' */
76 min = INF;
77 k = -1;
78 for(j=0; j<coins_num; j++) { /* Coins: ascending, and always contains '1' */
79 if(i >= coins[j]) {
80 if(min > changes_num[i-coins[j]]+1) {
81 min = changes_num[i-coins[j]]+1;
82 k = j;
83 }
84 } else
85 continue;
86 }
87 changes_num[i] = min;
88 changes[i] = coins[k];
89 }
90 }
91
92 int
93 main(int argc, char **argv)
94 {
95 while(is_continue()) {
96 input();
97 solve();
98 output();
99 }
100 }