[Math] Coin Change Problem with Fixed Coins

algorithmsapproximationinteger-partitionsintegersnp-complete

Problem: Given $n$ coin denominations, with $c_1<c_2<c_3<\cdots<c_{n}$ being positive integer numbers, and a number $X$, we want to know whether the number $X$ can be changed by $N$ coins.

Note that $N$ is fixed.
There are infinite number coins for each coin denomination.
For a coin denomination, more than one coins would be used to change $X$.

This problem is related to coin change problem, multiple-choice knapsack problem, $0$-$1$ knapsack problem, postage stamp problem, etc. However, it has differences with these problems.

Is this problem NP-complete?

How to solve this problem?

If you have ideas and suggestions, it's pleasure if you can share with me.

Thanks very much!

Best Answer

You've described an NP-complete problem. Indeed, this problem is exactly the subset-sum problem with the extra restriction that the desired subset has size $N$; but if this were not NP-complete then the subset-sum problem would not be either, because it would only take $|C|$ iterations of the "change-problem" algorithm to solve subset-sum (where $C$ is the set of coins). Subset-sum is NP-complete.

Actually, I've ignored that coins must have positive denomination. It remains NP-complete.

Related Solutions

[Math] Why is (European) money in units of $1,2,5,10,20,50, \cdots\;$

I think it's a mix between two facts:

1.- If Alice wants to buy something from Bob and both Alice and Bob have each one of every coin and note, it is guaranteed that Alice can buy that something regardless of the price (all numbers can be constructed with the money from Alice and the change that Bob can give her). The simplest way to do this would be to use powers of three for the currency. This is where the second fact comes in.

2.- We use the decimal system and 1,2,5 are the divisors of 10. So it makes it easier to compute what selections of coins and notes to use to pay for goods and serices.

[Math] Dynamic programming:Making a Change

Trying all possible solutions is an exhaustive search. The following is a dynamic programming algorithm. The minimal solution we search for can be defined recursively:

if m=v(k), for a k, then:
    coins_needed(m):=1, 
otherwise:   
    coins_needed(m):=
        min(coins_needed(1)+coins_needed(m-1),
        coins_needed(2)+coins_needed(m-2),
        ...,
        coins_needed(floor(m/2)+coins_needed(ceiling(m/2)))

One can start with m=1 and , then calculate coins_needed for m=2 and so on. It is important to store all the minimal solution one has calculated so far, otherwise the algorithm needs an exponential running time.

If one has calculated coins_needed(m-1) in this way, one has already calculated coins_needed(1),...,coins_needed(m-2) and stored the results. It is now easy to calculate coins(m) according to the above formula.

It is dynamic programming as defined in Wikipedia, The problem has optimal substructure, because the problem solution can be constructed of the solution of the smaller subproblems, and each subproblem can be broken in smaller sub problems again but we have overlapping subproblems. This means we have always the same sub problems that can be reused. So if we store the results of the subproblems (memoization) we can reuse them.

Best Answer

Related Solutions

[Math] Why is (European) money in units of $1,2,5,10,20,50, \cdots\;$

[Math] Dynamic programming:Making a Change

Related Question