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.

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.

Recommended Posts

Pensez au problème de changement minimum
À propos du problème du voyageur de commerce
À propos du problème du vendeur de patrouille commandé
Pensez grossièrement à la fonction de perte
Pensez grossièrement à la méthode de descente de gradient
À propos du test
Mon ami semble faire du python, alors pensez au problème ~ fizzbuzz ~
À propos de la file d'attente
Vous ne pouvez pas changer aspect_ratio avec sympy.plotting? À propos de l'affaire
[Python] Pensez sérieusement à la méthode gagnante M-1.
Pensez aux interfaces sélectives sur la ligne de commande
Réfléchissez à la programmation de Python sur votre iPad
Trier en Python. Pensons ensuite à l'algorithme.
Pensez à la nouvelle génération de Rack et WSGI
À propos de la fonction Déplier
À propos de la commande de service
À propos de la matrice de confusion
À propos du modèle de visiteur
Examiner le double problème
Pensez à l'environnement d'analyse (Partie 1: Vue d'ensemble) * Depuis janvier 2017
À propos de l'événement de changement de caméra de l'API Google Maps Android
Une histoire sur la façon de traiter le problème CORS
Résolvez le problème de Monty Hall
À propos du module Python venv
À propos de la fonction enumerate (python)
Changement de problème d'optimisation - problème plus réaliste -
À propos de la compréhension du lecteur en 3 points [...]
Changer le thème de Jupyter
Changer le style de matplotlib
À propos des composants de Luigi
À propos des fonctionnalités de Python
Pensez aux abandons avec MNIST
Réfléchissez aux raisons pour lesquelles Kubernetes est décrit comme «Linux dans le monde du cloud»
J'ai fait réfléchir AI aux paroles de Genshi Yonezu (pré-traitement)
J'ai fait réfléchir AI aux paroles de Genshi Yonezu (implémentation)