There are a lot of coin change questions and answers around but I couldn't find this one, and am wondering if it's even a coin change problem.
Basically I have a bunch of different coins, and an infinite amount of each coin.
So say there are stacks of various denominations. Each stack is infinite. (So infinite number of 25c coins, infinite number of 2c coins etc).
However, on top of each stack of coins is a special coin which has a value greater than (or equal) to the coins below. I can't access the coins below without using this coin on top.
What I'm trying to work out is the minimum number of coins required to make a certain sum.
I think this is solvable dynamic programming but I'm unsure how to add this limitation to the traditional solutions.
I was wondering if I should just remove the special coin in my list once I use it and replace it with the normal coins, but I can't seem to reason if that would break the algorithm or not.
Looks like a classic dynamic programming problem, where the challenge is to choose state correctly.
Usually, we choose sum of selected coins as problem state, and number of selected coins as state value. Transitions are every possible coin we can take. If we have 25c and 5c coins, we can move from state Sum with value Count to states Sum+25,count+1 and Sum+5,count+1.
For your limitation, state should be augmented with information about which special(top) coins were taken. So you add a bit for each stack of coins. Then you just need to define possible transitions from every state. It is simple: if a bit for stack is set, it means that top coin was already taken and you can add a non-top coin from that stack to state sum, keeping all bits the same. Otherwise, you can take the top coin from that stack, ad its value to state sum, and set related bit.
You start from state with sum 0, all bits clear and value 0, then build states from the lowest sum up to target.
At the end, you should iterate over all possible combinations of bits and. compare values for state with the target sum and that bits combination. Choose the minimum - that would be the answer.
Example solution code:
#Available coins: (top coin value, other coins value)
stacks = [(17,8),(5,3),(11,1),(6,4)]
#Target sum
target_value = 70
states = dict()
states[(0,0)] = (0,None,None)
#DP going from sum 0 to target sum, bottom up:
for value in xrange(0, target_value):
#For each sum, consider every possible combination of bits
for bits in xrange(0, 2 ** len(stacks)):
#Can we get to this sum with this bits?
if (value,bits) in states:
count = states[(value,bits)][0]
#Let's take coin from each stack
for stack in xrange(0, len(stacks)):
stack_bit = (1 << stack)
if bits & stack_bit:
#Top coin already used, take second
cost = stacks[stack][1]
transition = (value + cost, bits)
else:
#Top coin not yet used
cost = stacks[stack][0]
transition = (value + cost, bits | stack_bit)
#If we can get a better solution for state with sum and bits
#update it
if (not (transition in states)) or states[transition][0] > count + 1:
#First element is coins number
#Second is 'backtrack reference'
#Third is coin value for this step
states[transition] = (count+1, (value,bits), cost)
min_count = target_value + 1
min_state = None
#Find the best solution over all states with sum=target_value
for bits in xrange(0, 2 ** len(stacks)):
if (target_value,bits) in states:
count = states[(target_value,bits)][0]
if count < min_count:
min_count = count
min_state = (target_value, bits)
collected_coins = []
state = min_state
if state == None:
print "No solution"
else:
#Follow backtrack references to get individual coins
while state <> (0,0):
collected_coins.append(states[state][2])
state = states[state][1]
print "Solution: %s" % list(reversed(collected_coins))