[PYTHON] Denken Sie an das Problem der minimalen Änderung

Wie man das Fischen minimiert

Angenommen, dies ist die Situation in Ihrer Brieftasche.

1,000 Yen Rechnung:1 Blatt
100 Yen Ball:Drei
10 Yen Ball:1 Blatt
1 Yen Ball:1 Blatt

Nehmen Sie diese Brieftasche im Supermarkt

Preis:756 Yen

Welche Art von Zahlung soll ich beim Kauf leisten Wird die Anzahl der Änderungen am geringsten sein?

Wenn es ein Ärger ist, werde ich wahrscheinlich so bezahlen.

Zahlen Sie eine 1000-Yen-Rechnung
↓
1000-756=244 Yen ändern
↓
2*100
4*10
4*1
↓
Erhalten Sie insgesamt 10 Änderungen.

Damit ist Ihre Brieftasche Brötchen. Machen wir es uns etwas einfacher.

Zahlen Sie eine 1000-Yen-Rechnung
Zahlen Sie einen 10-Yen-Ball
↓
1010-756=254 Yen ändern
↓
1*200
1*50
4*1
↓
Erhalten Sie insgesamt 6 Änderungen.

Es hat ein wenig abgenommen. Kannst du nicht mehr tun?

Zahlen Sie eine 1000-Yen-Rechnung
Zahlen Sie 3 100 Yen Bälle
Zahlen Sie einen 10-Yen-Ball
Zahlen Sie 1 Yen Ball
↓
1311 Yen-756=555 Yen ändern
↓
1*500
1*50
1*5
↓
Erhalten Sie insgesamt 3 Änderungen.

Cool! Der Angestellte wird durch die mysteriöse Zahlung von 1311 Yen verwirrt sein. "Aber ich kann nicht zurück gehen ..." Die angezeigten 555 Yen Zeichen. Dies kann ein doy Gesicht sein. Sie können Veränderung mit einem triumphierenden Gesicht erhalten. Es muss von nun an mit dem ada-Namen Mach GO bezeichnet werden.

Lassen Sie es uns in das Programm setzen

Diesmal hat es funktioniert, aber wenn Sie einen kleinen Fehler bei der Berechnung machen, sind Sie nur eine seltsame Person. Um mit dem Angestellten ein Chaos zu machen, ohne Ihren Kopf zu benutzen, sollten Sie dies in das Programm aufnehmen Ich möchte darüber nachdenken. Wie kann es erreicht werden?

Wie wäre es mit einem Round-Robin mit dem folgenden Verfahren?

Listen Sie alle Geldkombinationen in Ihrer Brieftasche auf.
Nehmen Sie nur diejenigen heraus, deren Zahlungsbetrag den in Rechnung gestellten Betrag übersteigt.
Berechnen Sie die Anzahl jeder Änderung für alle verbleibenden Kombinationen.
Wählen Sie die mit der geringsten Änderung.

Round-Robin ... nicht schön. Vorerst ist es jedoch vorrangig, dies zu realisieren. Hier ist es.

`smart_pay.py`


# -*- coding: utf-8 -*-
import itertools
money_type = (10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)

def smart_pay(saifu,kakaku):
    bestPttern=None
    patterns=[]
    for mtype in money_type:
        pattern=[]
        for c in range(saifu[mtype]+1):
            pattern.append([mtype,c])
        if len(pattern)>1:
            patterns.append(pattern)
    for p in itertools.product(*patterns):
        ptn={x[0]:x[1] for x in p}
        if coins2price(ptn)>=kakaku:
            if  bestPttern is None:
                bestPttern=ptn
            else:
                if count_coins(price2coins(coins2price(bestPttern)-kakaku)) > count_coins(price2coins(coins2price(ptn)-kakaku)):
                    bestPttern=ptn
    return bestPttern

def price2coins(price):
    coins = {}
    for mt in money_type:
        coins[mt], price = divmod(price, mt)
    return coins

def coins2price(coins):
    return sum(key * val for key,val in coins.items())

def count_coins(coins):
    return sum(val for key,val in coins.items())

if __name__ == "__main__":
    saifu={}
    print("Zunächst werde ich Sie nach dem Inhalt Ihrer Brieftasche fragen...")
    for mtype in money_type:
        saifu[mtype]= int(raw_input(str(mtype)+ "Wie viele Kreise?\n>"))
    kakaku=int(raw_input("Wie viel kaufst du?\n>"))
    print("Die beste Zahlungsmethode.\n.\n.\n")
    bestPttern=smart_pay(saifu,kakaku)
    if bestPttern is None:
        print("Ich kann es kaum erwarten .. ..")
    else:
        for key,val in bestPttern.items():
            print(str(key)+"Yen"+str(val)+"Blatt")
        print("ist!")

Die Funktion der Methode sieht folgendermaßen aus.

price2coins: Geben Sie den Betrag ein und Sie erhalten die (ideale) Anzahl der Münzen.
coin2price: Wenn Sie Münzen einwerfen, wird der Betrag angezeigt.
count_coins: Zählt die Anzahl der Münzen.
smart_pay: Geben Sie den Inhalt Ihrer Brieftasche und den Kaufpreis ein und erfahren Sie die beste Zahlungsmethode.

Ich werde es sofort versuchen.

Zunächst werde ich Sie nach dem Inhalt Ihrer Brieftasche fragen...
Wie viele 10.000 Yen sind es?
>0
Wie viele 5000 Yen?
>0
Wie viele 2000 Yen?
>0
Wie viele 1000 Yen?
>1
Wie viele 500 Yen?
>0
Wie viele 100 Yen?
>3
Wie viele 50 Yen?
>0
Wie viele 10 Yen?
>1
Wie viele 5 Yen?
>0
Wie viele Blätter ist 1 Yen?
>1
Wie viel kaufst du?
>756
Die beste Zahlungsmethode.
.
.

Ein 1000 Yen
1 Yen 1 Blatt
1 Stück 10 Yen
3 Stück 100 Yen
ist!

Toll. Auf diese Weise können Sie nach Herzenslust im Supermarkt ein Chaos anrichten.

Ein kleiner Kommentar

coins[mt], price = divmod(price, mt) Ich bekomme den Preisbetrag geteilt durch mt (Nennwert des Geldes) und gleichzeitig zu viel. Python ist unglaublich.

return sum(key * val for key,val in coins.items()) Aus dem Wörterbuch namens Münzen (Schlüssel: Nennwert des Geldes, Wert: Anzahl der Münzen) SUM ist der Schlüsselwert, der von der for-Schleife herausgenommen und zu einem Array multipliziert wird. Python ist unglaublich.

for p in itertools.product(*patterns): Ein Array, in dem ein Array gespeichert ist, in dem die Anzahl der Münzen wie [500,2] und [100: 3] gespeichert ist. Ich habe es an itertools.product übergeben und die Round-Robin-Kombination in einer for-Schleife erhalten. Python ist unglaublich.

Zusammenfassung

Python ist unglaublich.