L'extrême nord du problème de la minimisation des pièces dans le portefeuille ~ La personne qui paie 1245 yens pour la comptabilité de 694 yens ~ a été évoqué il y a longtemps, il peut donc être résolu comme un problème de planification linéaire. J'ai fait. Puisque pulp peut être utilisée comme bibliothèque de modélisation en Python, utilisez pulp. Pour ceux qui ne sont pas doués pour utiliser la pulpe, je vais relier l'article suivant. Introduction à la résolution de problèmes de planification linéaire avec PuLP
Confirmé que 1245 yens seront payés pour un produit de 694 yens. Si vous regardez les commentaires dans la source ci-dessous, vous pouvez comprendre ce que vous faites. J'utilise deux types de variables, une variable de paiement et une variable de changement, mais j'ai réalisé qu'un type de variable de numéro de portefeuille après le paiement est en fait suffisant. Le sens de la formulation est remis en question. Lorsqu'il s'agit de problèmes à grande échelle, c'est mortel. De plus, le nombre de contenus dans le portefeuille ne se distingue pas par les pièces et les billets. Il vaut mieux minimiser le volume, pas le nombre de feuilles. [Une addition] Il y a des gens qui font beaucoup de recherches. À propos de l'optimisation des pièces dans votre portefeuille
MinimizeChange.py
import pulp
import numpy as np
#Genre d'argent
money_type = (10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)
#Quantité de marchandises
price = 694
#Le contenu du portefeuille (10000 à partir de la gauche, 5000,...）
purse = [1, 1, 1, 1, 0, 4, 0, 4, 1, 3]
#Créons un problème de minimisation...
problem = pulp.LpProblem('Change Minimization', pulp.LpMinimize)
#Le nombre variable de pièces de yens à utiliser
pay_var = np.array([pulp.LpVariable('pay_var_'+str(i),0,purse[k]+1,'Integer') for k,i in enumerate(money_type)])
#Variable combien de pièces de yens seront retournées comme monnaie
change_var = np.array([pulp.LpVariable('change_var_'+str(i),0,purse[k]+1,'Integer') for k,i in enumerate(money_type)])
'''
Fonction objective
Nombre de billets et de pièces dans le portefeuille après le paiement+Nombre de billets / pièces à payer* 0.01
Cette dernière section vise à éviter des résultats peu clairs comme payer 10 000 yens et récupérer 10 000 yens.
'''
problem += pulp.lpSum(purse - pay_var + change_var) + pulp.lpSum(pay_var)*0.01
#L'argent payé doit être supérieur au prix du produit.
problem += pulp.lpDot(money_type,pay_var) - price >= 0
#Changer le montant = 10000*10000 feuilles+5000*5000 feuilles+...+1*Doit être une seule feuille Restriction
problem += pulp.lpDot(money_type,change_var) == pulp.lpDot(money_type,pay_var) - price
#Vous ne pouvez pas payer plus que le numéro de votre portefeuille
for i,v in enumerate(purse):
problem += pay_var[i] - purse[i] <= 0
status = problem.solve()
print("Meilleur moyen de paiement")
for i,v in enumerate(pay_var):
print("{}Cercle{}Feuille".format(money_type[i],pay_var[i].value()))
print("Nombre de changements")
for i,v in enumerate(change_var):
print("{}Cercle{}Feuille".format(money_type[i],change_var[i].value()))
Si j'ai un portefeuille qui peut compter les pièces et les factures à l'intérieur, je peux recommander le montant du paiement chaque fois que j'effectue un paiement. On a l'impression que ça va à contre-courant, mais si vous avez un tel portefeuille, je l'achèterai pour le moment (rires).