The problem of minimizing change is the problem of thinking about payment so that the number of changes is minimized.
When I was thinking of "the problem of minimizing change," I suddenly wondered. As an example, consider the following:
1 500-yen coin: 4 100-yen coins: 9 10-yen coins: 9 1-yen coins for 499 yen
If you want to minimize ordinary change, you should get 4 100-yen coins, 9 10-yen coins, 9 1-yen coins and get 0 yen for fishing. …… But that's boring (if you're a human, you should take out one 500-yen coin and get a 1-yen coin as change)
Therefore, the problem to be considered from now on is the problem of minimizing change, which "minimizes the total number of payments and changes".
I decided to search all over and think about it. (Although it is undecided as of April 12, 2017) I would like to pay attention to the algorithm in the future, so I will implement it in 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
#For full search
all_coin_lists = [list(range(x+1)) for x in coin_list]
# product(*list)Full search with
for coin_list in product(*all_coin_lists):
#Each coin_Check the amount in list
this_price = list_price(coin_list)
#If coin_Process if the amount of list is more than price
if this_price >= price:
#Total number of payments and changes
temp = sum(get_change(this_price-price)) + sum(coin_list)
if min_ans >= temp:
min_pattern = coin_list[:]
min_ans = temp
return min_pattern
slow! (True face) The calculation time increases with the power of each number of money on hand. For example, it took an enormous amount of time to have all nine pieces of money ...
However, in a normal state (total of about 20 cards on hand), it can be calculated in about 5 seconds, so it's reasonable ...
As of now, the following can be considered as ideas for reducing the amount of calculation.
In the current full search, for example, for a payment of 319 yen, you may consider a payment method such as "3 100-yen coins, 2 10-yen coins". On the other hand, payment methods with completely overlapping parts such as "1 thousand yen bill, 3 100 yen coins, 2 10 yen coins" will also be searched. I want to exclude these duplicate payment methods.