Le problème de la minimisation du changement est celui de la réflexion sur le paiement qui minimise le nombre de changements.
Quand je pensais au «problème de minimiser le changement», je me suis soudain demandé. À titre d'exemple, considérez ce qui suit:
Une balle de 500 yens: 4 balles de 100 yens: 9 balles de 10 yens: 499 yens lorsqu'il y a 9 balles de 1 yen
Si vous voulez minimiser le changement ordinaire, vous devriez obtenir 4 balles de 100 yens, 9 balles de 10 yens, 9 balles de 1 yen et obtenir 0 yens pour la pêche. …… Mais c'est ennuyeux (si vous êtes un humain, vous devriez prendre une balle de 500 yens et obtenir une balle de 1 yen pour la monnaie)
Par conséquent, le problème à considérer à partir de maintenant est celui de la minimisation du changement, qui "minimise le nombre total de paiements et de changements".
J'ai décidé de chercher partout et d'y réfléchir. (Bien qu'il soit indécis au 12 avril 2017) Je voudrais faire attention à l'algorithme à l'avenir, je vais donc l'implémenter en Python.
Brute.py
# -*- coding: utf-8 -*-
from itertools import product
import sys
coins = (1,5,10,50,100,500,1000,5000,10000)
# return coin list of pay
def get_change(pay):
ans = []
for coin in reversed(coins):
if pay > coin:
ans.append(pay//coin)
pay %= coin
else :
ans.append(0)
ans.reverse()
return ans
# coin_list to price
def list_price(coin_list):
ans = 0
for index,coin in enumerate(coins):
ans += coin_list[index]*coin
return ans
# for debug
# show coin_list as 1yen : xx, 5yen : xx,...
def show_coin_list(coin_list):
for index,coin in enumerate(coins):
print(coin,end="")
print("yen: " , end="")
print(coin_list[index])
def Brute_algorithm(coin_list,price):
"""
Input : coin_list = [1-yen, 5-yen,...10k-yen]
price : price (integer)
Example :
coin_list = [2,1,5,0,4,1,2,0,0] -> 2957 yen
price = 499
"""
# ans is a coin_set
min_ans = sys.maxsize
#Pour une recherche complète
all_coin_lists = [list(range(x+1)) for x in coin_list]
# product(*list)Recherche complète avec
for coin_list in product(*all_coin_lists):
#Chaque pièce_Vérifiez le montant dans la liste
this_price = list_price(coin_list)
#Si pièce_Traiter si le montant de la liste est supérieur au prix
if this_price >= price:
#Nombre total de paiements et de modifications
temp = sum(get_change(this_price-price)) + sum(coin_list)
if min_ans >= temp:
min_pattern = coin_list[:]
min_ans = temp
return min_pattern
lent! (Vrai visage) Le temps de calcul augmentera avec la puissance de chaque pièce d'argent dont vous disposez. Par exemple, il a fallu énormément de temps pour avoir les neuf pièces d'argent ...
Cependant, dans un état normal (total d'environ 20 cartes en main), il peut être calculé en environ 5 secondes, donc c'est raisonnable ...
Actuellement, les éléments suivants peuvent être considérés comme des idées pour réduire la quantité de calcul.
Dans la recherche complète actuelle, par exemple, pour un paiement de 319 yens, vous pouvez penser à un mode de paiement tel que "3 balles de 100 yens, 2 balles de 10 yens". D'autre part, les méthodes de paiement avec des parties complètement superposées telles que «billet de mille yens, 3 boules de 100 yens, 2 boules de 10 yens» seront également recherchées. Je souhaite exclure ces modes de paiement en double.