## 2019年1月14日月曜日

### Algorithm - Python - メモリは役に立つ(両替方法、異なる解の個数、貪欲アルゴリズム、辞書の作成と検索、例外、再帰探索でのメモ化)

コード

Python 3

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

count = 0

def make_smart_change(
bills: list, target: int, highest: int, solution: list = []) -> None:
'''
>>> make_smart_change([1, 2, 5], 6, 1)
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[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 bill in bills:
if bill >= highest:
new_solution = solution[:] + [bill]
make_smart_change(bills, target, bill, new_solution)
return None

def make_smart_change_count(bills: list, size: int, target: int) -> int:
'''
>>> make_smart_change_count([1, 2, 5], 3, 6)
5
>>> make_smart_change_count([1, 2, 5, 10], 4, 16)
25
'''
if target == 0:
return 1
if target < 0:
return 0
if size == 0:
return 0
count1 = make_smart_change_count(bills, size-1, target)
count2 = make_smart_change_count(bills, size, target - bills[size-1])
return count1 + count2

def make_smart_change_count_memoized(
bills: list, size: int, target: int, memo: {}) -> int:
'''
>>> make_smart_change_count_memoized([1, 2, 5], 3, 6, {})
5
>>> make_smart_change_count_memoized([1, 2, 5, 10], 4, 16, {})
25
'''
if (size, target) in memo:
return memo[(size, target)]
if target == 0:
return 1
if target < 0:
return 0
if size == 0:
return 0
count1 = make_smart_change_count_memoized(bills, size-1, target, memo)
count2 = make_smart_change_count_memoized(
bills, size, target - bills[size-1], memo)

count0 = count1 + count2
memo[(size, target)] = count0
return count0

if __name__ == '__main__':
import doctest
doctest.testmod()
count = 0
make_smart_change([1, 2, 5], 6, 1)
print(count, count == 5)
count = 0
make_smart_change([1, 2, 5, 10], 16, 1)
print(count, count == 25)

import time
bills = list(range(1, 11))
target = 100
print(f'紙幣: {bills}、目標値: {target}')
start = time.time()
c = make_smart_change_count(bills, len(bills), target)
t = time.time() - start
print(f'メモ化無し: {c} {t}s')
start = time.time()
c = make_smart_change_count_memoized(bills, len(bills), target, {})
t = time.time() - start
print(f'メモ化有り: {c} {t}s')
```

```\$ python3 sample5.py -v
Trying:
make_smart_change([1, 2, 5], 6, 1)
Expecting:
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 2, 2]
[1, 5]
[2, 2, 2]
ok
Trying:
make_smart_change_count([1, 2, 5], 3, 6)
Expecting:
5
ok
Trying:
make_smart_change_count([1, 2, 5, 10], 4, 16)
Expecting:
25
ok
Trying:
make_smart_change_count_memoized([1, 2, 5], 3, 6, {})
Expecting:
5
ok
Trying:
make_smart_change_count_memoized([1, 2, 5, 10], 4, 16, {})
Expecting:
25
ok
__main__
3 items passed all tests:
1 tests in __main__.make_smart_change
2 tests in __main__.make_smart_change_count
2 tests in __main__.make_smart_change_count_memoized
5 tests in 4 items.
5 passed and 0 failed.
Test passed.
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 2, 2]
[1, 5]
[2, 2, 2]
5 True
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 2, 2, 5]
[1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 5, 5]
[1, 1, 1, 1, 1, 1, 10]
[1, 1, 1, 1, 1, 2, 2, 2, 5]
[1, 1, 1, 1, 2, 2, 2, 2, 2, 2]
[1, 1, 1, 1, 2, 5, 5]
[1, 1, 1, 1, 2, 10]
[1, 1, 1, 2, 2, 2, 2, 5]
[1, 1, 2, 2, 2, 2, 2, 2, 2]
[1, 1, 2, 2, 5, 5]
[1, 1, 2, 2, 10]
[1, 2, 2, 2, 2, 2, 5]
[1, 5, 5, 5]
[1, 5, 10]
[2, 2, 2, 2, 2, 2, 2, 2]
[2, 2, 2, 5, 5]
[2, 2, 2, 10]
25 True

メモ化無し: 6292069 33.50895714759827s
メモ化有り: 6292069 0.0007131099700927734s
\$
```