Pensez au problème de changement minimum

Comment minimiser la pêche

Supposons que ce soit la situation dans votre portefeuille.

1,Billet de 000 yens:1 feuille
Boule de 100 yens:Trois
Balle de 10 yens:1 feuille
1 boule de yen:1 feuille

Prenez ce portefeuille au dépanneur

prix:756 yens

Quel type de paiement dois-je effectuer lors de l'achat Le nombre de changements sera-t-il le plus petit?

Si c'est un problème, je paierai probablement de cette façon.

Payer une facture de 1000 yens
↓
1000-756=244 yens de change
↓
2*100
4*10
4*1
↓
Obtenez un total de 10 changements.

Avec cela, votre portefeuille est chignon. Faisons un peu plus facile.

Payer une facture de 1000 yens
Payez une balle de 10 yens
↓
1010-756=254 yens de change
↓
1*200
1*50
4*1
↓
Obtenez un total de 6 changements.

Il a un peu diminué. Tu ne peux pas faire plus?

Payer une facture de 1000 yens
Payez 3 boules de 100 yens
Payez une balle de 10 yens
Payer 1 boule de yen
↓
1311 yens-756=555 yens change
↓
1*500
1*50
1*5
↓
Obtenez un total de 3 changements.

Cool! Le greffier sera confus par le mystérieux paiement de 1311 yens. "Mais je ne peux pas revenir en arrière ..." Les 555 caractères yens affichés. Cela peut être un visage de doy. Vous pouvez recevoir du changement avec un visage triomphant. Il sera probablement appelé par le nom ada Mach GO à partir de maintenant.

Mettons-le dans le programme

Cette fois, cela a fonctionné, mais si vous faites une légère erreur dans le calcul, vous êtes juste une personne étrange. Afin de faire un désordre avec le greffier sans utiliser votre tête, vous devez le mettre dans le programme Je veux y réfléchir. Comment peut-on y arriver?

Pourquoi ne pas essayer un tournoi à la ronde avec la procédure suivante?

1. Dressez la liste de toutes les combinaisons d'argent dans votre portefeuille.
2. Ne retirez que ceux dont le montant du paiement dépasse le montant facturé.
3. Calculez le nombre de chaque changement pour toutes les combinaisons restantes.
4. Choisissez celui avec le moins de changement.

Round-robin ... pas beau. Mais pour le moment, la priorité est de le réaliser. Voilà.

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("Tout d'abord, je vais vous interroger sur le contenu de votre portefeuille...")
    for mtype in money_type:
        saifu[mtype]= int(raw_input(str(mtype)+ "Combien de cercles?\n>"))
    kakaku=int(raw_input("Combien achetez-vous?\n>"))
    print("Le meilleur moyen de paiement.\n.\n.\n")
    bestPttern=smart_pay(saifu,kakaku)
    if bestPttern is None:
        print("J'ai hâte. .. ..")
    else:
        for key,val in bestPttern.items():
            print(str(key)+"Yen"+str(val)+"Feuille")
        print("est!")

La fonction de la méthode ressemble à ceci.

• price2coins: Entrez le montant et il vous indiquera le nombre (idéal) de pièces.
• coins2price: Lorsque vous insérez des pièces, il vous indiquera le montant.
• count_coins: compte le nombre de pièces.
• smart_pay: Mettez le contenu de votre portefeuille et le prix d'achat et il vous indiquera le meilleur moyen de paiement.

Je vais l'essayer immédiatement.

Tout d'abord, je vais vous interroger sur le contenu de votre portefeuille...
Combien de 10 000 yens sont-ils?
>0
Combien de 5000 yens?
>0
Combien de 2000 yens?
>0
Combien de 1000 yens?
>1
Combien de 500 yens?
>0
Combien de 100 yens?
>3
Combien de 50 yens?
>0
Combien de 10 yens?
>1
Combien de 5 yens?
>0
Combien de feuilles font 1 yen?
>1
Combien achetez-vous?
>756
Le meilleur moyen de paiement.
.
.

Un 1000 yens
1 yen 1 feuille
1 pièce de 10 yens
3 pièces de 100 yens
est!

Génial. Avec cela, vous pouvez faire un gâchis au dépanneur à votre guise.

Un petit commentaire

coins[mt], price = divmod(price, mt) J'obtiens le montant du prix divisé par mt (valeur faciale de l'argent) et trop en même temps. Python est incroyable.

return sum(key * val for key,val in coins.items()) À partir du dictionnaire appelé pièces (clé: valeur faciale de l'argent, valeur: nombre de pièces) SUM est la valeur de clé extraite par la boucle for et multipliée pour créer un tableau. Python est incroyable.

for p in itertools.product(*patterns): Un tableau qui stocke un tableau qui stocke le nombre de pièces telles que [500,2] et [100: 3] Je l'ai passé à itertools.product et j'ai reçu la combinaison à tour de rôle dans une boucle for. Python est incroyable.

Résumé

Python est incroyable.