I was asked the other day to write down a program to solve one of these classical NP-complete problems, related to the knapsack problem. It is the change-making problem, where you have a certain value of money you must pay someone, and you want to use as few coins as possible. In the real world it’s easy to solve it using a “greedy” algorithm where you just divide the number with the largest coin denomination possible, then proceed doing this with the remaining amount. But for generic coin denominations, this is not possible.

Imagine that there is a 11 cents coin, a 10 cents coin, and a 1 cent coin. If you need to give 97 cents to someone, with the greedy algorithm you would first divide by 11, leaving 97-88=9 cents left. So you would end up giving 8 11-cents coins plus 9 1-cent coins, in a total of 17 coins. But you could have given instead 7 11-cents coins and two 10-cents coins, spending just 9 coins total.

Finding these solutions can be quite hard. This is a discrete optimization problem, like the Traveling Salesperson problem, or the N-queens puzzle and others… They are all usually approached by a search method, what means you must define a tree somehow. Your solution will be the sequence of branches you have chosen at each node. The leaves are the answers, and you must optimize something along the way.

In programming contests such as topcoder and others, and even in some real-world applications, when this problem shows up what you usually need is not to find a single solution for a given total and coins values. It often pays instead to generate a list of all the answers (for different values) for that coin set. Each node in the tree is a value, and each branch means “adding X money”. From each node we have a branch where we add each possible coin. So one way to solve the problem is to perform a breadth-first search in this tree. We want to find the first level of the three where the given value shows up (if it does).

The following Python code does exactly that: the solutions are just the number of coins needed (that is what I was asked, but it’s not difficult to use a list and actually record how many of the different coins you need). You store these solutions in a dictionary, where the index is the values. If a certain value is already in the dictionary, then that is the optimal answer, and when we produce it in the loop, the value should be discarded. If the values produces are new, then it’s a new answer. The loop iterates over the dictionary keys adding new answers…

#!/usr/bin/python ## Solution generator to the Change-making problem. ## Coded in Python by Nicolau Werneck <nwerneck@gmail.com> ## http://en.wikipedia.org/wiki/Change-making_problem ## The program grows a dictionary with the solutions, starting from 0 ## coins and until the desired value is obtained. It's a breadth-first ## tree traversal where new solutions are calculated from the ## previously calculated ones. from itertools import product import sys alvo = int(sys.stdin.read()) coins=[11,10,1] ## Coin denominations. sol = {0: 0} ## Initial solution array. k = 0 ## Initial coin count. while not alvo in sol: k+=1 ## Increment coin count. for v,m in product(sol.keys(),coins): ## For each child, if v+m>alvo: ## Skip large solutions. continue if not v+m in sol: ## If solution is new, sol[v+m]=k ## append solution. ## Print solution print sol[alvo]

What we are doing here is a famous dynamic programming technique, of storing the results of a recursive function to avoid having to re-calculate it repeatedly. I actually learned to do this in programming contests, it’s one thing I regret not having studied in college… The cool thing about this technique is that if instead of doing this, you try to calculate the solutions from the ground up every time, it gets very slow, and that’s why this is the perfect kind of problem for programming competitions.

But putting the competitions aside for a moment… What would be the other way? And what if I really need just a single solution, and my input value is so large that it starts to get impractical to store all that intermediary solutions?

Another way is to do a depth-first tree traversal, or perform backtracking. That means instead of looking for all we can do with 1, 2, 3… coins, we go on adding coins until we surpass the desired value. Than we go back the last coin, and replace it for another value, until we cross the bound again, and go back, and so on. This way we are sweeping that same tree, with the advantage that we don’t have to store all the intermediary solutions. One disadvantage is that we will only know the solution after we sweep the whole tree.

Every time I think of backtracking, it immediately makes me think of Prolog, this very cool programming language that is built around this concept. In prolog you just state the relations between entities, and “running the program” means performing this depth-first search on the non-provided variables until the relations are satisfied.

Although I think of Prolog every time I see such a problem, I rarely actually use it!… But this time I decided to give it a shot. So here is a first try to create a Prolog code to solve the change-making problem…

%% Generates all solutions for the change-making problem. Possible %% denominations are facts. This program is very sub-optimal because %% different combinations are not considered equal... But it's small %% and cute! vm(7). vm(5). vm(3). coins(0, [[], 0]). coins(V, [[M|Mx], K]) :- V > 0, vm(M), Vx is V - M, coins(Vx, [Mx, Kx]), K is Kx + 1.

This first program is very small and simple… What happens when you execute this is that Prolog will tell you combinations of coins that make the desired sum. But we are not optimizing yet… With the 97 example, above, and 11, 10 and 1 coins, it outputs:

Sol = [[11,11,11,11,11,11,11,11,1,1,1,1,1,1,1,1,1],17] ? ; Sol = [[11,11,11,11,11,11,11,10,10],9] ? ; Sol = [[11,11,11,11,11,11,11,10,1,1,1,1,1,1,1,1,1,1],18] ? ; Sol = [[11,11,11,11,11,11,11,1,11,1,1,1,1,1,1,1,1],17] ? ; Sol = [[11,11,11,11,11,11,11,1,10,1,1,1,1,1,1,1,1,1],18] ? ; Sol = [[11,11,11,11,11,11,11,1,1,11,1,1,1,1,1,1,1],17] ? ; Sol = [[11,11,11,11,11,11,11,1,1,10,1,1,1,1,1,1,1,1],18] ? ; Sol = [[11,11,11,11,11,11,11,1,1,1,11,1,1,1,1,1,1],17] ? ; Sol = [[11,11,11,11,11,11,11,1,1,1,10,1,1,1,1,1,1,1],18] ? ;

We were lucky that is produced the answer right in the second shot… That means it started to sweep the tree until if found a first good leaf. After that it “pretended it was bad” and started to look again, until it found this second answer. This could go and on until all the possibilities were tested. The last possibility would have 97 1-cent coins.

There is something obviously bad about this program. We are spending too much time looking at alternatives that mean just the same. We are taking in consideration the order of the coins, while that doesn’t matter, but just the amount of each denomination!

This is classic mistake people do (as I did…) when starting to solve problems like this. And the classic fix is to change to program to choose at each node on all the possibilities of a specific element. So in the root node we now choose the number of 11-cents coins, then on the second level we choose the 10-cents, and on the leaves we choose how many 1-cent coins (easy task). Notice how previously the height of the tree was related to the quantity of coins, and the branches to the coin options. Now each level is related to an option, and the branches to the quantity. We kind of swapped possible roles of the variables in the algorithm…

The following code performs this search on the quantities, with a single coin value being considered at each level. We did another important modification here: instead of a predicate telling us the possible coin values, now we have list with the values that we pop to see the current value, and use the rest in the recursive call.

We also have a predicate that produces a sequence of decreasing numbers from a given start, all the way down to 0. In a procedural language that is very easy to do, it’s the good old “for” loop. In Prolog the more natural way to do is to generate a list with the values… This way I did the new values are produced “in the backtracking way”. I’m not sure if there is a better way to do it like this… We use these decreasing numbers to sweep the tree. There is an heuristics going on here: I am starting with larger coins and larger quantities, because even though the greedy algorithm is not optimal, it still tells something about this problem.

%% Generate all solutions for the change-making problem. %% %% execute with, e.g.: %% gprolog --entry-goal "['coin-sols.pl']" --query-goal "coins(81, [11,10,1], Sol)" %% This predicate generates all number from A to 0, in decrescent %% order. It would be more natural in Prolog to generate a list with %% all values... This way it looks ugly. gera_dec(A,A) :- A>=0. gera_dec(A,C) :- A>0, gera_dec(A,B), ( B=1, C=0, ! ; C is B-1 ). %% This is the main predicate. The first argument is the total ammount %% of money we need to reach. The second argument is a list of the %% possible coin values, or denominations. The third argument will %% become the anwer, a list with the quantities of each coin to %% satisfy the Value. coins(0,[],[]). coins(0, [M|Mx], [L|Lx]) :- L is 0, coins(0, Mx, Lx). coins(Valor, [M|T], [A|Lt]) :- Valor>0, Ax is Valor // M, %% Sweep the possibilities starting from the maximum possible %% value for that denomination. gera_dec(Ax,K), %% Follow recursively solving the problem for the remaining %% value and the smaller coins. Res is (Valor - (K*M)), coins(Res, T, Lt), A is K.

This program produces the following output:

Sol = [8,0,9] ? ; Sol = [7,2,0] ? ; Sol = [7,1,10] ? ; Sol = [7,0,20] ? ; Sol = [6,3,1] ? ; Sol = [6,2,11] ? ; Sol = [6,1,21] ? ; Sol = [6,0,31] ? ; Sol = [5,4,2] ? ; (...)

The solution is there again at the second answer: 7 11-cents coins plus 2 10-cents. But now we are not losing time with different combinations. The program can find all the 53 solutions in a few milliseconds on my Atom netbook… For the value of 197 it took 860ms, and 12 seconds for 397.

This program is still not optimizing, but just sweeping the space of possible coin combinations. To minimize the coins quantity we would need to keep track of what is the best solution found while we move by the three. We would also be able to stop searching inside paths that would obviously lead just to solutions worse than the one we know…

Doing that all starts to get complicated, and there are also all sorts of clever trick we can do to speed computation. Therefore once you got grasp of the problem, the best thing to do is to forget about implementing better solutions, and go for a dedicated library!

As I said previously, these are very classical problems, and there are many real-world applications that boil down to them. There are C libraries, Python libraries, commercial programs…

Because Prolog is so close to the nature of these problems, it became common to see Prolog systems with finite-domain solver capabilities. One of them is GNU Prolog, or gprolog, that is also able to create executable programs from your Prolog code.

The documentation of gprolog is still a bit poor, but I managed to use it in my problem, and the result is this:

%% Solve the change-making problem, and return the minimum number of %% coins needed. This code reads the desired value, and a list of %% possible coin values (denominations) from the stdin. the list %% begins with the number of different coins. It solves the problem %% using the finite domain solver capabilities of gprolog. %% Execute with, e.g.: %% echo $'97\n3\n1\n10\n11' | gprolog --entry-goal "['fd-mo.pl']" --query-goal "init" %% Predicat to calculate the sum of the values in a vector. vec_sum([],0). vec_sum([M|Mx],S) :- vec_sum(Mx,Sx), S = M+Sx. %% Predicate to calculate a vectorial product. vec_mult([],_,0). vec_mult(_,[],0). vec_mult([A|Ax], [B|Bx], S) :- vec_mult(Ax, Bx, Sx), S = A*B+Sx. %% This predicate generates a list of fd variables, one for each %% possible coin value, and limit them according to the next larger %% coin. The limit could be smaller, but it would be harder to %% calculate. The first limit is based on the desired total value. gera_list(_,[],[]). gera_list(Max, [D|Dx], [M|Mx]) :- fd_domain(M, 0, Max), gera_list(D, Dx, Mx). pop([D|_],D). %% Picks up first list element. %% This predicate does the hard work. It generate the list of %% variables, then sets the restriction that sum of all coins should %% be the desired parameter. Then starts the fd_minimize to find %% answers with the smallest possible number of coins. solve(Val, Deno, K) :- pop(Deno, First), Max is Val // First, gera_list(Max, Deno, Vars), vec_mult(Deno, Vars, S), S #= Val, vec_sum(Vars, Sum), K #= Sum, fd_minimize(fd_labeling(Vars), K). %% This predicate reads a list of K numbers from the standard input, %% in reversed order... It's ugly. read_denoms(0,[]). read_denoms(K,[Z|Zx]) :- K>0, Kx is K-1, read_denoms(Kx,Zx), read_integer(Z). %% Initialization. Reads desired value, then the list of coin %% denominations, then solve and print answer. init :- read_integer(Val), read_integer(K), read_denoms(K,Z), solve(Val, Z, Sol), write(Sol),nl, halt(0). :- initialization(init).

The program is quite large, but also quite general. First of all, it reads the parameters from the standard input, so you can compile this program and use it for any case. (I hope I get in a programming contest in the future where this code tun out to be useful =) ). You need to enter the values one at each line. First the amount of money, then the list of possible coins. Before the list, you must enter the number of items in the list (quite lame and old-school thing to do, sorry, but that’s how it gets easy. 😦 )

The way the FD solver works here is this: you first declare the variables, then you state the restrictions of your problem (using the #= operator in this case), and then you execute the fd_minimize on the variables, minimizing the variable K, which is the number of coins.

This program doesn’t look too much “Prolog-y” to me anymore. We are just using a certain FD library to solve the problem!… But again, that would happen to any language when we start using a library instead of implementing everything.

The FD solver is quite powerful. This problem is one of the simplest ones it can handle. These examples by professor Jomi Hübner show some more complicated possibilities.

This code with the fd_minimize can find the solution for 397, and 11, 10 1 and coins in very few milliseconds in my computer… In fact I started to grow this number, and the program didn’t start to get slow. What I am having are problems with the number input… The Python implementation above starts to get slow when the value gets over 1000 or 2000. Now I wanted to compare the speed of this last Prolog-based FD sover, compiled, with solutions with other languages and libraries…

PS: Please WordPress, support Prolog in the syntax-highlighting!… 🙂

waganeThis is a message for Nic. I saw a comment that you wrote saying you wanted to buy a bluetooth keyboard. I have one ofthe Nokia ones I bought about 4 years ago when I didn’t have internet connection at home. Have not used it since I got internet at home but would be willing to sell it for a reasonable price. It cost me £80 4 years ago and is still in great condition. Anyway, I guess you have my email so let me know.

nlw0Post authorThanks, but no. I’m looking for something small and (very) affordable…