## 2018年12月25日火曜日

### Algorithm - Python - 両替する方法を数える(紙幣の枚数の制限、最小枚数の解、組合せの再帰生成)

コード(Emacs)

Python 3

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

count = 0

def make_smart_change(money: list, target: int, highest: int,
minimum_solution: list, solution: list = []) -> None:
'''
>>> minimum_solution = []
>>> make_smart_change([(1, 3), (2, 3), (5, 1)], 6, 1, minimum_solution)
>>> print(minimum_solution)
[1, 5]
'''
global count
total = sum(solution)
if total == target:
if len(minimum_solution) == 0 or len(solution) < len(minimum_solution):
minimum_solution.clear()
for n in solution:
minimum_solution.append(n)
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,
minimum_solution, new_solution)
return None

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

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