The far north of the wallet minimization problem ~ The person who pays 1245 yen for the accounting of 694 yen ~ was talked about a long time ago, so it can be solved as a linear programming problem. I did it. Since pulp can be used as a modeling library in Python, pulp is used. For those who are not good at using pulp, I will link the following article. Introduction to solving linear programming problems with PuLP
Confirmed that 1245 yen will be paid for a product of 694 yen. You can understand what you are doing by looking at the comments in the source below. I use two types of variables, a payment variable and a change variable, but I realized that one type of variable for the number of wallets after payment is actually sufficient. The sense of formulation is questioned. When it comes to large-scale problems, this is deadly. Also, the number of contents in the wallet is not distinguished by coins and banknotes. It's better to minimize the volume, not the number of sheets. [Addition] There are people who are doing a lot of research. About optimizing coins in your wallet
MinimizeChange.py
import pulp
import numpy as np
#Kind of money
money_type = (10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)
#Amount of goods
price = 694
#The contents of the wallet (10,000 from the left, 5,000,...）
purse = [1, 1, 1, 1, 0, 4, 0, 4, 1, 3]
#Let's create a minimization problem...
problem = pulp.LpProblem('Change Minimization', pulp.LpMinimize)
#Variable how many yen coins to use
pay_var = np.array([pulp.LpVariable('pay_var_'+str(i),0,purse[k]+1,'Integer') for k,i in enumerate(money_type)])
#Variable how many yen coins will be returned as change
change_var = np.array([pulp.LpVariable('change_var_'+str(i),0,purse[k]+1,'Integer') for k,i in enumerate(money_type)])
'''
Objective function
Number of bills and coins in the wallet after checkout+Number of bills / coins to pay* 0.01
The latter section is to avoid unclear results such as paying 10,000 yen and getting 10,000 yen back.
'''
problem += pulp.lpSum(purse - pay_var + change_var) + pulp.lpSum(pay_var)*0.01
#The money paid must be larger than the product price.
problem += pulp.lpDot(money_type,pay_var) - price >= 0
#Change amount = 10000*10000 sheets+5000*5000 sheets+...+1*It must be one sheet
problem += pulp.lpDot(money_type,change_var) == pulp.lpDot(money_type,pay_var) - price
#You can't pay more than the number in your wallet
for i,v in enumerate(purse):
problem += pay_var[i] - purse[i] <= 0
status = problem.solve()
print("Best payment method")
for i,v in enumerate(pay_var):
print("{}Circle{}Sheet".format(money_type[i],pay_var[i].value()))
print("Number of changes")
for i,v in enumerate(change_var):
print("{}Circle{}Sheet".format(money_type[i],change_var[i].value()))
If I have a wallet that can count the coins and banknotes inside, I can recommend the payment amount every time I check out. It feels like it's going against the times, but if you have such a wallet, I'll buy it for the time being (laughs) If you're interested, give it a try!