## 2018年12月24日月曜日

### Algorithm - Python - 両替する方法を数える(紙幣の枚数の制限、効率的な再帰探索、組合せの再帰生成)

コード(Emacs)

Python 3

```#!/usr/bin/env python3

count = 0

def make_smart_change(
money: list, target: int, highest: int, solution: list = []) -> None:
'''
>>> make_smart_change([(1, 3), (2, 3), (5, 1)], 6, 1)
[1, 1, 2, 2]
[1, 5]
[2, 2, 2]
'''
global count
total = sum(solution)
if total == target:
print(solution)
count += 1
return None
if total > target:
return None
for i, (bill, rest) in enumerate(money):
if bill >= highest:
new_solution = solution[:] + [bill]
rest -= 1
if rest == 0:
new_money = money[1:]
else:
new_money = money[:]
new_money[i] = (bill, rest - 1)
make_smart_change(new_money, target, bill, new_solution)
return None

if __name__ == '__main__':
import doctest
doctest.testmod()
```

```\$ ./sample2.py -v
Trying:
make_smart_change([(1, 3), (2, 3), (5, 1)], 6, 1)
Expecting:
[1, 1, 2, 2]
[1, 5]
[2, 2, 2]
ok
__main__
1 items passed all tests:
1 tests in __main__.make_smart_change
1 tests in 2 items.
1 passed and 0 failed.
Test passed.
\$
```