-
Notifications
You must be signed in to change notification settings - Fork 4
/
coin-changing.c
56 lines (43 loc) 路 1.34 KB
/
coin-changing.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>
int coins_n, amount;
int *coins;
int *dp;
int *coin_used;
int min(int a, int b) { return a <= b ? a : b; }
void optimally_exchange(int amount) {
int exchange_amount, i;
for (exchange_amount = 1; exchange_amount <= amount; exchange_amount++)
dp[exchange_amount] = 1 << 16;
dp[0] = 0;
for (exchange_amount = 1; exchange_amount <= amount; exchange_amount++)
for (i = 0; i < coins_n; i++)
if (coins[i] <= exchange_amount)
if (1 + dp[exchange_amount - coins[i]] < dp[exchange_amount])
dp[exchange_amount] = 1 + dp[exchange_amount - coins[i]],
coin_used[exchange_amount] = coins[i];
}
void print_exchange(int n) {
printf("%d", coin_used[n]);
if (n - coin_used[n])
printf(" + "), print_exchange(n - coin_used[n]);
}
int main() {
int i;
scanf("%d %d", &coins_n, &amount);
coins = (int *)malloc(sizeof(int) * (coins_n));
dp = (int *)malloc(sizeof(int) * (amount + 1));
coin_used = (int *)malloc(sizeof(int) * (amount + 1));
for (i = 0; i < coins_n; i++)
scanf("%d", &coins[i]);
for (i = 0; i < coins_n; i++)
printf("%d\n", coins[i]);
optimally_exchange(amount);
printf("optimal exchange uses %d coins\n", dp[amount]);
printf("optimal change is %d = ", amount);
print_exchange(amount);
free(coins);
free(dp);
free(coin_used);
return 0;
}