Cela ressemble à un problème de programmation dynamique classique, où le défi consiste à choisir l'état correctement.
Habituellement, nous choisissons la somme des pièces sélectionnées comme état de problème, et le nombre de pièces sélectionnées comme valeur d'état. Les transitions sont toutes les pièces que nous pouvons prendre. Si nous avons des pièces 25c et 5c, nous pouvons passer de l'état Sum à la valeur Count aux états Sum+25,count+1 et Sum+5,count+1.
Pour votre limitation, l'état devrait être augmenté avec des informations sur les pièces spéciales (en haut) qui ont été prises. Donc vous ajoutez un peu pour chaque pile de pièces de monnaie. Ensuite, vous avez juste besoin de définir les transitions possibles de chaque état. C'est simple: si un bit pour la pile est positionné, cela signifie que la pièce supérieure a déjà été prise et que vous pouvez ajouter une pièce non-supérieure de cette pile à la somme des états, en gardant tous les bits identiques. Sinon, vous pouvez prendre la pièce supérieure de cette pile, ajouter sa valeur à la somme d'état et définir le bit associé.
Vous démarrez à partir de l'état avec la somme 0, tous les bits sont effacés et la valeur 0, puis les états de construction de la somme la plus basse jusqu'à la cible. A la fin, vous devriez itérer sur toutes les combinaisons possibles de bits et. comparez les valeurs de l'état avec la somme cible et la combinaison de bits. Choisissez le minimum - ce serait la réponse.
Exemple code solution:
#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))
Il est essentiellement le changement de pièce DP. Vous devriez travailler une pile de pièces à la fois, avec une mise à jour de DP légèrement plus compliquée. –
Au moment où je pense à calculer les pièces minimales pour chaque valeur de 0 jusqu'à la somme (comme la solution traditionnelle). Pour ce faire, je vérifie chaque pile, en itérant sur une liste de piles L. Si je trouve que la somme des sommes est complétée en utilisant la pièce spéciale d'une pile. Je vais remplacer cette pièce spéciale par la pièce régulière (dans la liste L), et ça restera comme ça pour toujours. – Eric