/*---------------------------------------------------------------------- File : change.c Contents: compute the number of ways to change a given amount of money Author : Christian Borgelt History : 14.11.1997 file created 17.11.1997 nested loops version added (v.1) 18.11.1997 recursive version added (v.2) 19.11.1997 some comments added 07.04.1998 dynamic programming solutions added 13.05.1998 multiple table version removed ----------------------------------------------------------------------*/ #include #include #ifndef VERSION #define VERSION 5 /* default: compile fifth version */ #endif /*---------------------------------------------------------------------- An explanation of this way of using conditional compilation is given in the program `perfect.c'. It enables choosing the version with a compiler option (-D for the Gnu C-compiler). ----------------------------------------------------------------------*/ #if (VERSION != 1) /* if not to compile first version */ /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ #define UNITCNT 15 /* number of money units */ /*---------------------------------------------------------------------- Constants ----------------------------------------------------------------------*/ const int unitvals[UNITCNT] = { /* money unit values */ 1, 2, 5, /* 1, 2 and 5 Pfennig */ 10, 50, /* 10 and 50 Pfennig */ 100, 200, 500, /* 1, 2 and 5 DM */ 1000, 2000, 5000, /* 10, 20 and 50 DM */ 10000, 20000, 50000, /* 100, 200 and 500 DM */ 100000 /* 1000 DM */ }; #endif /* #if (VERSION != 1) */ /*---------------------------------------------------------------------- The preprocessor definition and the constant vector above just fix the number of different money units and their values. These definitions make it much easier to change the money system (at least for versions 2 to 5, version 1 has the money system built in). ----------------------------------------------------------------------*/ #if (VERSION == 3) /* if to compile the third version */ const int steps[UNITCNT] = { /* step widths for the tables */ 0, 0, 5, /* according to the money units */ 10, 50, /* These values are used in the */ 100, 100, 100, /* third version to determine the */ 1000, 1000, 1000, /* appropriate index in the lookup */ 10000, 10000, 10000, /* tables. See below (comment on */ 100000 /* the third version) for a more */ }; /* detailed explanation */ #endif /* #if (VERSION == 3) */ /*---------------------------------------------------------------------- Global Variables ----------------------------------------------------------------------*/ #if (VERSION == 4) /* if to compile fourth version */ double tab[1000001]; /* dynamic programming table */ #endif /* #if (VERSION == 4) */ #if (VERSION == 5) /* if to compile fifth version */ double tab[200001]; /* dynamic programming table */ #endif /* #if (VERSION == 5) */ /*---------------------------------------------------------------------- Functions ----------------------------------------------------------------------*/ #if (VERSION == 1) /* if to compile the first version */ double count (int amount) { /* --- compute number of ways to */ /* change the amount `amount' */ int a500, a200, a100, a050, a020, a010, a005, a002, a001; int a_50, a_10, a_05, a_02; double n = 0; /* number of ways to change amount */ for (a500 = amount; a500 >= 0; a500 -= 100000) for (a200 = a500; a200 >= 0; a200 -= 50000) for (a100 = a200; a100 >= 0; a100 -= 20000) for (a050 = a100; a050 >= 0; a050 -= 10000) for (a020 = a050; a020 >= 0; a020 -= 5000) for (a010 = a020; a010 >= 0; a010 -= 2000) for (a005 = a010; a005 >= 0; a005 -= 1000) for (a002 = a005; a002 >= 0; a002 -= 500) for (a001 = a002; a001 >= 0; a001 -= 200) for (a_50 = a001; a_50 >= 0; a_50 -= 100) for (a_10 = a_50; a_10 >= 0; a_10 -= 50) for (a_05 = a_10; a_05 >= 0; a_05 -= 10) for (a_02 = a_05; a_02 >= 0; a_02 -= 5) n += a_02 /2 +1; return n; /* return computed number of ways */ } /* count() */ #endif /* #if (VERSION == 1) */ /*---------------------------------------------------------------------- This function implements the most direct approach to the money exchange problem. Each for-loop corresponds to a money unit. The first loop, for example, corresponds to 1000.00 DM = 100000 Pfennig, the fifth loop to 20.00 DM = 2000 Pfennig. The variable names are chosen according to the following scheme: `axxx' holds an amount that has to changed with money units whose value is less than or equal to xxx DM, `a_yy' an amount that has to be changed with money units whose value is less than or equal to yy Pfennig. Let u be the money unit corresponding to an arbitrary but fixed loop. Then this loop tries first all ways to change the amount that is passed to it from the next higher loop with zero units u, then with one unit u, two units u, and so on, until the amount cannot be reduced any further using money unit u. In each step the remaining amount (that is, the amount passed to the loop diminished by the value of the number of units u that have been removed by the loop up to that step) is passed to the next lower loop to compute the number of ways to change it with money units whose value is less than that of u. The innermost loop has been optimized. This loop, if it were there, would correspond to the money unit with value 2 (2 Pfennig) and in it the variable `n' would be increment in each step. Since the value that is computed by such a loop can be easily calculated, the loop is replaced by the statement `n += a_02/2 +1;' Note that this solution has the money system built in. If you want to change the money system, you will have to rewrite the loops. Of course, one could use the elements of the constant vector defined above as decrements, but even then the number of money units would still be fixed to be 15 (since there are 14 loops, one of which has been optimized --- see above). ----------------------------------------------------------------------*/ #if (VERSION == 2) /* if to compile the second version */ double count (int amount, int maxunit) { /* --- change amount using only units */ /* less than or equal to maxunit */ double n; /* number of ways to change amount */ if (maxunit < 2) /* if to use only 1 and 2 Pfennig, */ return amount/unitvals[1] +1; /* compute number of ways directly */ for (n = 0; amount >= 0; amount -= unitvals[maxunit]) n += count(amount, maxunit-1); /* compute number of ways to */ return n; /* change the amount and return it */ } /* count() */ #endif /* #if (VERSION == 2) */ /*---------------------------------------------------------------------- This solution replaces the nested loops used in version 1 by only one loop and a recursive call. Each level of the recursion corresponds to one loop level in version 1. This makes it possible to write the function independent of the money system used, since the depth of the recursion is controlled by the parameter `maxunit' and the value of a money unit is retrieved from the vector `unitvals'. To change the money system, only the preprocessor definition of UNITCNT and the constant vector `unitvals' have to be adapted. Again the innermost loop (innermost recursion) has been optimized, i.e. has been replaced by the expression `amount/unitvals[1] +1'. ----------------------------------------------------------------------*/ #if (VERSION == 3) /* if to compile the third version */ double count (int amount) { /* --- compute number of ways to */ /* change the amount `amount' */ int i; /* loop variable */ int cnts[UNITCNT]; /* money unit counters */ double n = 1; /* number of ways to change amount */ for (i = UNITCNT; --i > 0; ) cnts[i] = 0; cnts[0] = amount; /* start with smallest units only */ while (++i < UNITCNT) { /* traverse units > smallest unit */ if (unitvals[i] <= cnts[0]) { /* if one more unit i is possible */ cnts[0] -= unitvals[i]; /* replace unitvals[i] smallest units */ cnts[i]++; /* by one money unit i, */ n += 1; /* count the way found, */ i = 0; } /* and restart the loop */ else { /* if no more units i are possible */ cnts[0] += cnts[i] *unitvals[i]; cnts[i] = 0; /* change the amount in money units i */ } /* back to the smallest unit and */ } /* continue with the next money unit */ return n; /* return computed number of ways */ } /* count() */ #endif /* #if (VERSION == 3) */ /*---------------------------------------------------------------------- This function keeps the current combination of money units in a vector `cnts' and uses a loop to construct all possible combinations by working on this vector, i.e. by constructing a new combination from the current one. The idea is as follows: We start with smallest money units only, i.e. with `amount' Pfennigs. Then we start the loop to traverse the money units larger than the smallest unit. In the loop we test whether we can increase the number of money units i by one. If this is possible, we can construct a new way to change the amount by replacing an equivalent number of smallest units by one of the current unit. We count this way and then we restart the loop, i.e. we go back to the second smallest money unit. This is necessary, since after we increased the number of money units other than the second smallest, we have to test whether we can use one more of the second smallest money unit. E.g. after we increased the number of 5 Pfennig coins to change a given amount, we have to try to change the new remainder using 1 and 2 Pfennig coins. We restart the loop by resetting i to zero. This may not be a very clean way to do this, since it leads to a rather strange behaviour of the while loop. If you do not like this, you can replace the `i = 0' by a `break' and surround the while loop with a do-while loop, whose condition is '(i < UNITCNT)'. Then the outer while loop restarts the inner while loop as long as the inner loop is aborted by the `break'. In this manner the inner loop constructs a new way to change the amount and the outer loops traverses these ways. To make this even clearer the `n++' can be moved out of the inner while loop (provided n is initialized to 0, since the last execution of the outer loop does not construct a new way to change `amount'). If in the while loop we found that no more money units i can be used, we change the corresponding amount back to smallest money units. It is obvious that we did not find a new way to change `amount' in this case. Then the loop reexecutes and we try to increase the number of the next larger money unit, since we obviously tried all combinations with the current number of this larger money unit. We thus end up with an algorithm that has a structure very similar to the nested loop solution. The only difference is that the loop variables are kept in a vector and a loop through this vector is used to find the next combination of values for the loop variables. ----------------------------------------------------------------------*/ #if (VERSION == 4) /* if to compile fourth version */ double count (int amount) { /* --- compute number of ways to */ /* change the amount `amount' */ int i, k, n; /* loop variables and table index */ tab[0] = 1; /* one way to change amount 0 */ for (i = 0; i < UNITCNT; i++) /* traverse money units and amounts */ for (n = 0, k = unitvals[i]; k <= amount; ) tab[k++] += tab[n++]; /* use recursive formula */ return tab[amount]; /* return the result */ } /* count() */ #endif /* #if (VERSION == 4) */ /*--------------------------------------------------------------------*/ #if (VERSION == 5) /* if to compile fifth version */ double count (int amount) { /* --- compute number of ways to */ /* change the amount `amount' */ int i, k, n; /* loop variables and table index */ int u2 = unitvals[2]; /* buffer for unitvals[2] */ for (k = amount %u2; k <= amount; k += u2) tab[k/u2] = k/unitvals[1]+1;/* compute initial table */ for (i = 2; i < UNITCNT; i++) /* traverse money units and amounts */ for (n = 0, k = unitvals[i]/u2; k *u2 <= amount; ) tab[k++] += tab[n++]; /* use recursive formula */ return tab[amount/u2]; /* return the result */ } /* count() */ #endif /* #if (VERSION == 5) */ /*---------------------------------------------------------------------- These versions solve the problem with dynamic programming. The idea underlying this approach is the following: Let c(u_1, ..., u_n, a) be a function that states the number of ways to change amount a with money units u_1 to u_n. Let v(u_i) be the value of money unit u_i. Then the following recursive formula holds: c(u_1, ..., u_n, a) / 0, if n <= 0 or a < 0, = | 1, if a = 0, \ c(u_1, ..., u_{n-1}, a) + c(u_1, ..., u_n, a - v(u_n)), otherwise. The last line of this definition simply says, that to change amount a, we can use no money unit u_n and change a with units u_1 to u_{n-1} (this is represented by the term c(u_1, ..., u_{n-1}, a)) or we can use one money unit u_n and change the remainder of the amount a, that is, a - v(u_n), with money units u_1 to u_n (this is represented by the term c(u_1, ..., u_n, a - v(u_n))). (Compare the dynamic programming solution of the knapsack problem). This recursive formula is used directly in version 5. The drawback of this method is that it needs a very large table (with amount +1 elements). But such a large table is necessary only, if the size of the money units is not fixed. If we use a money unit system in which the smallest unit has value 1 and all money units larger than the third are multiples of the third (as it is the case for the German money system used in this program), we can reduce the table size. In this case the function of version 5 can be used. ----------------------------------------------------------------------*/ int main (int argc, char *argv[]) { /* --- main function */ double amount; /* amount to change in DM */ if (argc != 2) { /* if wrong number of arguments given */ printf("usage: %s x\n", argv[0]); printf("compute number of ways to change amount x (in DM)\n"); return 0; /* print a usage message */ } /* and abort the program */ amount = atof(argv[1]); /* convert argument to a number */ if ((amount <= 0.0) /* check range of amount */ || (amount > 10000.0)) { /* (must be within table range) */ printf("%s: illegal amount (0.01-10000.00)\n", argv[0]); return 1; } #if (VERSION == 2) /* if second version */ printf("%.15g\n", count((int)(amount *100), UNITCNT-1)); #else /* other versions */ printf("%.15g\n", count((int)(amount *100))); #endif /* #if (VERSION == 1) .. #else .. */ return 0; /* print number and return 'ok' */ } /* main() */ /*---------------------------------------------------------------------- The only thing worth noting in this function is that the call to the function `count' differs for version 2 on the one hand and all other version on the other. Hence we need conditional compilation to call `count' correctly. Exercise: Using version 2 it is very simple to allow an additional argument u to state the largest money unit to be used. The same can be done for version 3, 4 and 5, if the largest money unit is given as a parameter to the function `count' of these versions. Implement these extensions! ----------------------------------------------------------------------*/