2
$\begingroup$

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite supply of coins and also where we only have 1 of each coin. I was able to quickly implement the solution for the first scenario using a recursive formula from here but was not able to find a recursive formula for the second case and I instead came up with an iterative solution.

We can just sum every possible combination of coins, check and see if the sum is equal to the target wanted and compare the number of coins used to the current lowest number of coins. I also realized that I can use binary counting to simulate all possible combinations using the bits in the iterator as a coefficient (either 1 or 0) for each coin and then calculate the Hamming Weight to check how many coins was used in the sum.

To visualize an example with 3 coins:

C1 C2 C3 | S                        | W
 0  0  0 | 0 * C1 + 0 * C2 + 0 * C3 | 0
 0  0  1 | 0 * C1 + 0 * C2 + 1 * C3 | 1
 0  1  0 | 0 * C1 + 1 * C2 + 0 * C3 | 1
 0  1  1 | 0 * C1 + 1 * C2 + 1 * C3 | 2
 1  0  0 | 1 * C1 + 0 * C2 + 0 * C3 | 1
 1  0  1 | 1 * C1 + 0 * C2 + 1 * C3 | 2
 1  1  0 | 1 * C1 + 1 * C2 + 0 * C3 | 2
 1  1  1 | 1 * C1 + 1 * C2 + 1 * C3 | 3

Obviously we can omit the case where all the coefficients are 0, but for completeness (when target = 0) and simplicity I've kept it in the solution.

My implementation in Python is:

import math


def least_coins(coins, target):
    least = math.inf

    # loop all 2^n possible sums of coins
    for i in range(2 ** len(coins)):
        sum = 0

        # add all the coins multiplied by their coefficient in this iteration
        for j in range(len(coins)):
            # get the j-th bit in i
            coefficient = i >> j & 1
            sum += coefficient * coins[j]

        if sum == target:
            count = 0
            # calculate the Hamming Weight of i to determine the number of coins used
            while i:
                i &= i - 1
                count += 1
            least = min(least, count)

    return least


coins = [3, 1, 1, 3, 2, 4]
target = 10
print(least_coins(coins, target))
>>> 3
# 3 + 3 + 4 = 10

As you can see the coins are not necessarily unique, but can only be used once. How can I turn this into a recursive formula (if possible and for the reason of possibly being able to optimize it using dynamic programming) or even introduce coefficients other than 0 and 1 so the problem can be more general where we have a certain amount of each coin?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Let $N(t,S)$ be the least number of values from $S$ which sum to $t$. The basic recurrence is $$ N(t, S \cup \{s\}) = \min(N(t,S),N(t-s,S)+1). $$ I'll let you work out the details.

This recurrence leads to an efficient algorithm only if we are allowed to run in time polynomial in $t$.

If we think of $t$ encoded in binary, then this algorithm runs in exponential time.

Indeed, the very related SUBSET-SUM problem is NP-complete.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Missing a +1 for the $N(t-s, S)$ case? $\endgroup$
    – j_random_hacker
    Mar 10, 2020 at 16:37
  • $\begingroup$ Right, thanks for the correction! $\endgroup$
    – Yuval Filmus
    Mar 10, 2020 at 16:38
  • $\begingroup$ Just to clarify, is $\{s\}$ a set which contains only a specific item in the original $S$ and I should thus iterate all the elements in the original $S$ and get the min value of all the iterations? $\endgroup$
    – Rikus Honey
    Mar 11, 2020 at 18:14
  • $\begingroup$ In fact, $s \notin S$. Also, there’s no reason to iterate over all elements of the input set; you can pick one arbitrarily. $\endgroup$
    – Yuval Filmus
    Mar 11, 2020 at 18:16
  • $\begingroup$ @YuvalFilmus Thanks for the clarification, I was able to implement it as $N(t, m) = min(N(t, m - 1), N(t - S_m, m - 1) + 1)$ where $S \in \{S_1, S_2, ..., S_m\}$ Maybe you could add this to your answer? $\endgroup$
    – Rikus Honey
    Mar 11, 2020 at 18:50

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.