Das Problem der Minimierung von Änderungen ist das Problem, über Zahlungen nachzudenken, die die Anzahl der Änderungen minimieren.
Als ich an "das Problem der Minimierung von Veränderungen" dachte, fragte ich mich plötzlich. Betrachten Sie als Beispiel Folgendes:
Ein 500-Yen-Ball: 4 100-Yen-Bälle: 9 10-Yen-Bälle: 499 Yen, wenn 9 1-Yen-Bälle vorhanden sind
Wenn Sie die normale Veränderung minimieren möchten, sollten Sie 4 Bälle mit 100 Yen, 9 Bälle mit 10 Yen, 9 Bälle mit 1 Yen und 0 Yen zum Angeln erhalten. …… Aber das ist langweilig (wenn Sie ein Mensch sind, sollten Sie einen 500-Yen-Ball und einen 1-Yen-Ball zum Wechseln bekommen)
Daher ist das Problem, das von nun an zu berücksichtigen ist, das Problem der Minimierung von Änderungen, das "die Gesamtzahl der Zahlungen und Änderungen minimiert".
Ich beschloss, überall zu suchen und darüber nachzudenken. (Obwohl es ab dem 12. April 2017 noch unentschlossen ist) Ich möchte in Zukunft auf den Algorithmus achten, daher werde ich ihn in Python implementieren.
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
#Für die vollständige Suche
all_coin_lists = [list(range(x+1)) for x in coin_list]
# product(*list)Vollständige Suche mit
for coin_list in product(*all_coin_lists):
#Jede Münze_Überprüfen Sie den Betrag in der Liste
this_price = list_price(coin_list)
#Wenn Münze_Verarbeiten, wenn der Betrag in der Liste mehr als der Preis ist
if this_price >= price:
#Gesamtzahl der Zahlungen und Änderungen
temp = sum(get_change(this_price-price)) + sum(coin_list)
if min_ans >= temp:
min_pattern = coin_list[:]
min_ans = temp
return min_pattern
langsam! (Wahres Gesicht) Die Berechnungszeit erhöht sich mit der Leistung jedes Geldstücks, das Sie haben. Zum Beispiel hat es enorm viel Zeit gekostet, alle neun Geldstücke zu haben ...
In einem normalen Zustand (insgesamt ca. 20 Karten verfügbar) kann dies jedoch in ca. 5 Sekunden berechnet werden. Es ist also vernünftig ...
Derzeit kann Folgendes als Ideen zur Reduzierung des Rechenaufwands angesehen werden.
Bei der aktuellen vollständigen Suche, zum Beispiel für eine Zahlung von 319 Yen, können Sie sich eine Zahlungsmethode wie "3 100-Yen-Bälle, 2 10-Yen-Bälle" vorstellen. Andererseits werden auch Zahlungsmethoden mit vollständig überlappenden Teilen wie "1000-Yen-Rechnung, 3 100-Yen-Bälle, 2 10-Yen-Bälle" gesucht. Ich möchte diese doppelten Zahlungsmethoden ausschließen.