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))
