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 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?