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

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 コミュニケーション Network ssh 将棋 Data visualization Docker Econometrics VSCode statistical inference GitHub Pages apt development システム管理 Coffee cloud 数値計算 素数 Book Font Metrics Poetry Ubuntu 24.04 LTS architecture aws shell systemctl テンプレート データ構造 ポワソン分布 会計分析 文字コード 環境構築 論文 App Bayesian Dynamic Programming Keyboard Processing R Steam filesystem quarto regex