1
$\begingroup$

There is the classical version of the minimum coins to make change problem where the change and the set of coins available are all integers. Given an infinite amount of each type of coin, we're asked the smallest number of coins required to make change for a given amount. This can be solved with dynamic programming, Python code below. The code will return $\infty$ when the amount can't be made.

def coinsChg(coins, amount):
   dp_array = [np.inf for i in range(amount+1)]
   dp_array[0] = 0
   for coin in coins:
      for j in range(coin, amount+1):
         dp_array[j] = min(dp_array[j], dp_array[j-coin]+1)
   return dp_array[-1]

This got me thinking about the case where the coins and the amount to be constructed can be any real numbers and not just integers. One complication is that we can't express real numbers exactly on a computer, complicating the question of whether or not the amount can be made exactly. So let's say we restrict ourselves to rational numbers. For the coins and the amount, we are given the numerators and the denominators. Now, given the integer arrays of coin numerators, coin denominators, the amount numerator and amount denominator, we need to return the smallest number of coins to make the amount exactly. If this isn't possible, the algorithm should return $\infty$ like before. Dynamic programming seems to be out of the question now. So what is a good algorithm for solving this? Is it NP-hard?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Am I wrong or isn't it sufficient to multiply the coin values and the target amount by the LCM of the denominators to turn the problem to integers ? $\endgroup$
    – user16034
    Jun 14 at 8:54
  • $\begingroup$ If you limit yourself to rationals, and the set of available coins is finite, then this is exactly the same as the integer problem. $\endgroup$
    – Stef
    Jun 14 at 10:23
  • $\begingroup$ @YvesDaoust - if all the coins have denominators 2 or 3 but the amount has denominator 7, then it shouldn't be possible to make the amount exactly (unless the numerators just make everything an integer). But your approach will incorrectly conclude it is possible. $\endgroup$
    – Rohit Pandey
    Jun 14 at 20:09
  • 1
    $\begingroup$ @RohitPandey: so my first hypothesis was correct. Thanks. $\endgroup$
    – user16034
    Jun 14 at 20:24
  • $\begingroup$ Actually, never mind. It actually does work. You can multiply the coins and amount with any number you wish and the problem shouldn't change. But then how does this level with @D.W. answer? $\endgroup$
    – Rohit Pandey
    Jun 14 at 20:36

1 Answer 1

Reset to default
1
$\begingroup$

Unfortunately, it is NP-hard, by reduction from the subset sum problem.

The reduction is trivial: let $S$ be a set of integers, and $T$ a target sum (i.e., an instance of the subset-sum problem). Consider the following change-making problem: let $S$ be the set of coin denominations, and $T$ be the desired change. Then there exists a way to make change for $T$ using these coins, iff there is a subset of $S$ that sums to $T$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi. Could you give a link to the reduction? $\endgroup$
    – Stef
    Jun 14 at 10:24
  • $\begingroup$ @Stef, see updated answer $\endgroup$
    – D.W. ♦
    Jun 14 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.