コインの両替問題とプログラミング

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

1
2
3
4
5
6
7
8
9
10
target = 200
coin_list = [1, 2, 5, 10, 20, 50, 100, 200]
ways = [1] + [0]*target

for coin in coin_list:
    for i in range(coin, target + 1):
        ways[i] += ways[i - coin]

print(ways[target])
>>> 73682

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def find_steps(n):
    if not isinstance(n, int) or n <= 0:
        raise ValueError('the input must be a positive integer')

    if n == 1:
        return 1

    elif n == 2:
        return 2
    
    elif n == 3:
        return 3

    else:
        return find_steps(n-1) + find_steps(n-3)

1
2
print(find_steps(15))
>>> 277

1
2
n m
c1 c2 ... cm

1
2
15 6
1 2 7 8 12 50

1
2

1
2
3
4
5
6
7
8
9
10
11
12
13
def get_coin_greedy(target, coin_list):
    coin = 0
    coin_list = sorted(coin_list, reverse = True)
    for i in coin_list:
        coin_tmp, target = divmod(target, i)
        coin += coin_tmp
        if target == 0:
            break
    
    return coin

print(get_coin_greedy(15, [1, 2, 7, 8, 9]))
>>> 4

1
2
3
4
5
6
7
8
9
10
11
12
13
def get_coin(target, coin_list):
    ways = [0] + [target] * target
    coin_list = sorted(coin_list)

    for i in range(target+1):
        for j in coin_list:
            tmp = i - j
            ways[i] = min(ways[tmp if tmp >= 0 else -1] + 1, ways[i])
    
    return ways[-1]

print(get_coin(15, [1,2,7,8, 9]))
>>> 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Find_Coin_Combination():
    def __init__(self, target, coin_list):
        self.target = target
        self.coin_list = coin_list
        self.coin_path = None
        self.minimum_coin_num = None
        self.coin_combination = None
        
    def get_coin(self):
        ways = [0] + [self.target] * self.target
        self.coin_path = [0]*(self.target+1)

        for i in range(1, self.target+1):
            for j in self.coin_list:
                tmp = i - j
                if ways[tmp if tmp >= 0 else -1] + 1 <= ways[i]:
                    self.coin_path[i] = j
                    ways[i] = min(ways[tmp if tmp >= 0 else -1] + 1, ways[i])
        
        self.minimum_coin_num = ways[-1]
    
    def print_result(self):
        tmp_target = self.target
        self.coin_combination = dict(zip(self.coin_list ,[0]*len(self.coin_list)))

        while tmp_target > 0:
             tmp_coin = self.coin_path[tmp_target]
             self.coin_combination[tmp_coin] += 1
             tmp_target -= tmp_coin
        
        return self.minimum_coin_num, self.coin_combination

coin_instance = Find_Coin_Combination(2345, [1, 2, 7, 8, 12, 25, 100])
coin_instance.get_coin()
print(coin_instance.print_result())
>>> (26, {1: 0, 2: 0, 7: 0, 8: 1, 12: 1, 25: 1, 100: 23})

統計 Python math Linux Ubuntu 20.04 LTS Shell English git Ubuntu 22.04 LTS 方法論 統計検定 競技プログラミング フーリエ解析 前処理 SQL coding 将棋 Data visualization Network statistical inference VSCode apt システム管理 Coffee Docker Econometrics GitHub Pages cloud 数値計算 素数 Book Font Metrics Poetry architecture aws shell ssh systemctl テンプレート データ構造 ポワソン分布 会計分析 文字コード 環境構築 論文 App Bayesian Dynamic Programming Keyboard Processing R Steam filesystem regex