Modified minimum coin change

Question

Suppose you have a K dollars Bill. Given 4 coins of value {1,4,6,9} Find the minimum number of coins the sum of which is K, when K is represented in Binary, meaning input's length is log(K)

I've tried Dynamic programming, but i didn't figure it out. Does anybody has any idea of how to start solving that ? It's related to knapsack problem somehow but i can't figure it out.

Thank you.

Answer 1

How about checking the number of coins as a function of K%9? Then you can translate it to the function of log(K).

Let K%9 = r, i.e. there is an integer n such that K = 9n + r, and r is between 0 and 8 inclusive.

• r=0: we need n coins of value 9,
• r=1: we need n coins of value 9 + 1 coin of value 1 = n+1 coins
• r=2: we need n coins of value 9 + 2 coins of value 1 = n+2 coins
• r=3: we need (n-1) coins of value 9 + 2 coins of value 6 = n+1 coin, or 3 coins of value 1 if K=3
• r=4: we need n coins of value 9 + 1 coin of value 4 = n+1 coins
• r=5: we need n coins of value 9 + 1 coin of value 4 + 1 coin of value 1 = n+2 coins
• r=6: we need n coins of value 9 + 1 coin of value 6 = n+1 coins
• r=7: we need n coins of value 9 + 1 coin of value 6 + 1 coin of value 1 = n+2 coins
• r=8: we need n coins of value 9 + 2 coins of value 4 = n+2 coins

Proofs: For the case r=0: we know that we can do it with n coins. If we were using m coins, m < n, than the max total value is m * 9, 9 being the max value of the coin. But 9m is less than K=9n, so we cannot use m coins to get K

For the cases where we have r=1, r=3, r=4 and r=6: following the same reasoning as above, we know that n coins would be enough (9n < K, K being 9n +r), and we know how to do it with n+1 coins.

For the cases r=2, r=5 and r=8 For the total amount, K, K%3=(9n+r)%3=r%3=2; for the values of the coins, 6%3=0 and 9%3=0, but 1%3=1 and 4%3=1. Therefore, to get K we need at (2+3j) coins of values 1 or 4. Now we need to prove that, if we use n+1 coins, and at least 2 coins are of values 1 or 4, we cannot get K. Indeed, the max value of n+1 coins is 9*(n-1) + 2*4 = 9n-1, this is less than K=9n+r.

Finally, for the case r=7: Suppose we use n+1 coin. All of them is 9, we get 9*(n+1), this is not we want. If at least one of them is not 9, than the total value is at most 9n + 6, 6 being the second most valuable coins, this is not enough. Thus, n+1 is not enough. And we know how to get it with n+2. Voila!

Answer 2

The canonical dynamic program for this problem loops j from 0 to K, computing each time the minimum number of coins to make change for a j-dollar bill. When j = 0, zero coins is optimal. For each other j, the answer is one coin plus the minimum for j - 1, j - 4, j - 6, or j - 9 (when those quantities are nonnegative). For other sets of denominations, replace 1, 4, 6, 9 appropriately.

To derive a table as Yulia V did, one can show that, for every set of denominations, when K is sufficiently large, optimal change includes a coin of largest denomination. Loop j up from 0, looking for exceptions, where an exception is when it takes more coins to make j - 9 dollars than j (or when j - 9 is negative). After 9 non-exceptions in a row, there can be no more exceptions. (For other sets of denominations, substitute the largest denomination for 9 in the foregoing text.)

Answer 3

Use dynamic programming on K mod 36, then use 9s for the rest, where 36 = lcm(1, 4, 6, 9).