Suppose this is the situation in your wallet.
1,000 yen bill:1 sheet
100 yen ball:Three
10 Yen coin:1 sheet
1 Yen coin:1 sheet
Take this wallet at a convenience store
price:756 yen
What kind of payment should I make when buying a product? Will the number of changes be the smallest?
If it's a hassle, I'll probably pay this way.
Pay one 1000 yen bill
↓
1000-756=244 yen change
↓
2*100
4*10
4*1
↓
Get a total of 10 changes.
With this, your wallet is bun. Let's make it a little easier.
Pay one 1000 yen bill
Pay one 10-yen coin
↓
1010-756=254 yen change
↓
1*200
1*50
4*1
↓
Get a total of 6 changes.
It has decreased a little. Can't you do more?
Pay one 1000 yen bill
Pay 3 100 yen balls
Pay one 10-yen coin
Pay one 1-yen coin
↓
1311 yen-756=555 yen change
↓
1*500
1*50
1*5
↓
Get a total of 3 changes.
Cool! The clerk will be confused by the mysterious payment of 1311 yen. "But I can't go back ..." The displayed 555 yen characters. This can be a sloppy face. You can receive change with a triumphant face. Probably it must be called by the ada name Mach GO from now on.
This time it worked, but if you make a slight mistake in the calculation, you're just a weird person. In order to make a mess on the clerk without using your head, put this into the program I want to consider it. How can it be achieved?
How about trying a brute force attack with the following procedure?
Brute force ... not beautiful. But for the time being, the priority is to realize it. Here is it.
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("First of all, I will ask you about the contents of your wallet...")
for mtype in money_type:
saifu[mtype]= int(raw_input(str(mtype)+ "How many circles are there?\n>"))
kakaku=int(raw_input("How much do you buy?\n>"))
print("The best payment method is.\n.\n.\n")
bestPttern=smart_pay(saifu,kakaku)
if bestPttern is None:
print("I can't wait. .. ..")
else:
for key,val in bestPttern.items():
print(str(key)+"Yen"+str(val)+"Sheet")
print("is!")
The function of the method looks like this.
I will try it immediately.
First of all, I will ask you about the contents of your wallet...
How many 10,000 yen is it?
>0
How many 5000 yen?
>0
How many 2000 yen?
>0
How many 1000 yen?
>1
How many 500 yen?
>0
How many 100 yen?
>3
How many 50 yen?
>0
How many 10 yen?
>1
How many 5 yen?
>0
How many 1 yen is it?
>1
How much do you buy?
>756
The best payment method is.
.
.
One 1000 yen
1 yen
One 10 yen coin
3 pieces of 100 yen
is!
Great. With this, you can make a mess at the convenience store to your heart's content.
coins[mt], price = divmod(price, mt) I get the amount of price divided by mt (the face value of money) and too much at the same time. Python is amazing.
return sum(key * val for key,val in coins.items()) From a dictionary called coins (key: face value of money, value: number of coins) It is SUM that the KeyValue is taken out by the for loop and multiplied to make an array. Python is amazing.
for p in itertools.product(*patterns): An array that stores an array that stores the number of coins such as [500,2] and [100: 3] I pass it to itertools.product and receive the brute force combination in a for loop. Python is amazing.
Python is amazing.
Recommended Posts