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?