Solving Linear Equations in Natural Numbers

Description of the problem

Here is a classical problem:

Given that you have dominations of 1, 5, 10, 25 and 100 cent change, find the combination with fewest number of coins that sums up to a given amount N.

I will rephrase the problem as follows: given N , minimize $x+y+z+t+u$ subject to the condition $x+5y+10z+25t+100u=N$.

Second part of this problem, namely, finding a subsequence from given a sequence of numbers $x_1,...,x_m$ that sums up to a given number $N$ is called subset sum problem, and it is an NP complete problem.

I will give a minimally smart brute force solution: I will list all possible solutions and then take the one which satisfy the minimality condition.

Stumbling towards a solution

At the first go, one can set a naive upper bound on each of the variables: xx can’t be larger than N, while $y$ can’t be larger than $⌊N/5⌋$ etc. If you think about it, since we want to minimize the number of coins, there is another sequence of upper bounds: why would I use five 1 cents if I can use one nickel? So, the upper bound for $x$ is $min(5,N)$ while for $y$ we have $min(2,N)$ etc.

In general, if we need to minimize $x_1+⋯+x_m$ subject to the condition \[a_1x_1+⋯+a_mx_m=N\] we are going to have \[\ x_i < \min\left(\left\lceil\frac{N}{a_i}\right\rceil,\frac{lcm(a_i,a_j)}{a_i}\mid\ j\neq i\right) \] where $lcm(a,b)$ denotes the least common multiple of two numbers $a$ and $b$.

Then we search for a solution within that search space.

An implementation

I am going to need the following helper routines: The first is a macro I got used to using from clojure:

(defmacro ->> (x &rest forms)
  (dolist (f forms x)
    (if (listp f)
        (setf x (append f (list x)))
        (setf x (list f x)))))

->>

The second is something I got used to using from R:

(defun rep (k n &optional acc)
  (if (> n 0)
      (rep k (1- n) (cons k acc))
      acc))

REP

The following function generates the list of upper bounds I talked about above. It returns a list of coins.

(defun generate-pool (amount coins)
  (->> coins
       (maplist (lambda (xs)
                  (let ((x (car xs))
                        (ys (cdr xs)))
                    (reduce #'min
                            (cons (floor amount x)
                                  (mapcar (lambda (y) (1- (/ (lcm x y) x))) ys))))))
       (mapcan #'rep coins)
       (remove-if #'null)))

GENERATE-POOL

The main engine is a recursive function. If all dominations are greater than the amount, then there is no solution. If the amount is equal to one of the dominations, then that’s the solution. Otherwise remove each coins one by one, and search for a solution.

(defun engine (amount pool &optional (acc '(nil)))
  (cond ((or (null pool) (< amount (car pool))) nil)
        ((= amount (car pool)) (mapcar (lambda (xs) (cons amount xs)) acc))
        (t (append (engine (- amount (car pool))
                           (cdr pool)
                           (mapcar (lambda (xs) (cons (car pool) xs)) acc))
                   (engine amount (cdr pool) acc)))))

ENGINE

Finally, the entry point:

(defun change (amount coins)
  (remove-duplicates (engine amount (generate-pool amount coins))
                     :test #'equal))

CHANGE

Let us test:

(format nil "~{~a~%~}" (change 49 '(1 5 10 25 100)))
(format nil "~{~a~%~}" (change 63 '(1 5 10 21 100)))
(format nil "~{~a~%~}" (change 999 '(1 2 5 10 20 50 100)))

(10 10 10 10 5 1 1 1 1)
(25 10 10 1 1 1 1)

(10 10 10 10 10 10 1 1 1)
(21 10 10 10 10 1 1)
(21 21 10 10 1)
(21 21 21)

(100 100 100 100 100 100 100 100 100 20 20 20 20 10 2 2 2 2 1)
(100 100 100 100 100 100 100 100 100 50 20 20 2 2 2 2 1)
(100 100 100 100 100 100 100 100 100 20 20 20 20 10 5 2 2)
(100 100 100 100 100 100 100 100 100 50 20 20 5 2 2)