Money change problem: Greedy vs. Dyn.Pro.

 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

This algorithm, of time complexity <strong>O(A)</strong>, doesn't work for some (rare) situations.

## When Greedy is not enough
<del datetime="2010-01-18T10:41:49+00:00">The Greedy algorithm doesn't work for Denominations where if <strong>2 denominations D[i] and D[j] exists</strong> with:</del>


* <del datetime="2010-01-18T10:41:49+00:00"><strong>i &lt; j</strong></del>

* <del datetime="2010-01-18T10:41:49+00:00"><strong>D[i] &lt; D[j]</strong></del>

* <del datetime="2010-01-18T10:41:49+00:00"><strong>2 * D[i] &gt; D[j]</strong></del>



<del datetime="2010-01-18T10:41:49+00:00">For example, taken <strong>D = {1, 10, 30, 40}</strong> and amount <strong>A = 63</strong>, the Greedy algorithm will build a solution <strong>S = {3, 2, 0, 1}</strong>, that is sub-optimal. The optimal solution in this case is <strong>S = {3, 0, 2, 0}</strong>.</del>
<strong>UPDATE:</strong> [In the comments Vincenzo](#comment-11505) gives an example where this condition doesn't still stand but the Greedy Algorithm still produces the best solution.

## Dynamically Programmed Solution
In real life the Greedy algorithm should be always enough: I couldn't find any money system that has the problem described above. And, indeed, the Greedy approach is what every human being "normally" applies when changing money.

But we are Comp-Sci, and we need to find a better solution ;-) - a Dynamically Programmed one.

Given the function <strong>M[j], that is the minimum number of coins to make the amount 'j'</strong>, it looks like:


* <strong>M[A] = min<sub>[i = 0 -> n-1]</sub> { M[ A - D[i] ] +1 , M[A] }</strong>



Here is the code:

```c
unsigned int* change_coins_dynpro(unsigned short int D[],
    unsigned int D_size, unsigned int amount) {
    // Min. num. of coins for the given 'amount'
    unsigned int min_num_coins[amount], cur_min_num_coins;
    // Biggest coin used for the given 'amount'
    unsigned int biggest_coin_at[amount], cur_biggest_coin_at;
    
    unsigned int i, j;
    unsigned int* solution = NULL;
    
    // Ensure the Denomination System can represent any value
    if ( D[0] != 1 ) return NULL;
    
    // Initialize the solution array to Zero
    solution = (unsigned int*)calloc(D_size, sizeof(unsigned int));
    if ( NULL == solution ) {
        return NULL;
    }

    // Amount '0' requires '0' coins
    min_num_coins[0] = 0;
    biggest_coin_at[0] = 0;
    
    // For Amounts from '1' to 'amount'
    for ( i = 1; i <= amount; ++i ) {
        // Start taking 'D[0]' 'i-times'
        cur_min_num_coins = (i / D[0]);
        cur_biggest_coin_at = 0;

        // For coins from 'D[1]' to 'D[D_size -1]'
        for ( j = 1; j < D_size; ++j ) {
            // If 'D[j]' minimizes the num. of coins to take for amount 'i'
            if ( (i >= D[j]) && (cur_min_num_coins >= (min_num_coins[ i - D[j] ] +1)) ) {
                cur_min_num_coins = min_num_coins[ i - D[j] ] +1;
                cur_biggest_coin_at = j;
            }
        }
        
        // Store the minimum just found
        min_num_coins[i] = cur_min_num_coins;
        biggest_coin_at[i] = cur_biggest_coin_at;
    }
    
    // Let's build the solution array
    while ( amount > 0 ) {
        cur_biggest_coin_at = biggest_coin_at[amount];
        
        solution[ cur_biggest_coin_at ] += 1; // Add '1' of this coin to the solution
        amount -= D[cur_biggest_coin_at]; // Amount left when picking this coin
    }
    
    return solution;
}