Задача Из Проекта Эйлера, 31 (Сумма Монет)


Я только что закончил проект Эйлера 31: монета суммы, в которой просит сколькими способами можно составить £2, используя британские монеты (1р, 2р, 5р, 10р, 20р, 50р, £1 и £2).

Когда я сравнивал свой код и алгоритмы проблема обзора, я обнаружил, что мой код был быстрее, чем у них. Оба из них используют динамическое программирование, но по некоторым неизвестным причинам, мой код соответствует рекурсивный предел.

Проект Эйлера Ссылка

def problem_31_dynamic_programming(money, coin_index):
    count = 0
    if coin_index <= 0:
        return 1
    m = money
    if memoiz_list[m][coin_index] > 0:
        return memoiz_list[m][coin_index]
    while money >= 0:
        count += problem_31_dynamic_programming(money, coin_index - 1)
        money -= coin_list[coin_index]
    memoiz_list[m][coin_index] = count
    return count

Мое решение

import time

def problem_31(money, coin_index): #My solution (cannot solve big number such as 10000)
    if coin_index < 0:
        return 0
    if coin_index == 0 or money == 0:
        return 1
    if memoiz_list[money][coin_index] > 0:
        return memoiz_list[money][coin_index]
    if coin_list[coin_index] > money:
        return problem_31(money, coin_index - 1)
    memoiz_list[money][coin_index] = problem_31(money, coin_index-1)+ \
                                     problem_31(money-coin_list[coin_index],coin_index)
    return memoiz_list[money][coin_index]


start = time.time()
coin_list = [1,2,5,10,20,50,100,200]
memoiz_list = [[0,0,0,0,0,0,0,0] for i in range(201)]
print(problem_31_dynamic_programming(200,7)) #Replace problem_31_dynamic_programming() with problem_31
elapsed = time.time() - start
print("Result found in %f seconds"%(elapsed))


Комментарии
1 ответ

Глубина анализа

Немного настройки вашего кода приводит к результатам о максимальная глубина вызова:

def problem_31_a(money, coin_index, depth=1):
global glob_depth
glob_depth = max(glob_depth, depth)
count = 0
if coin_index <= 0:
return 1
m = money
if memoiz_list[m][coin_index] > 0:
return memoiz_list[m][coin_index]
while money >= 0:
count += problem_31_a(money, coin_index - 1, depth=depth+1)
money -= coin_list[coin_index]
memoiz_list[m][coin_index] = count
return count

def problem_31_b(money, coin_index, depth=1):
global glob_depth
glob_depth = max(glob_depth, depth)
if coin_index < 0:
return 0
if coin_index == 0 or money == 0:
return 1
if memoiz_list[money][coin_index] > 0:
return memoiz_list[money][coin_index]
if coin_list[coin_index] > money:
return problem_31_b(money, coin_index - 1, depth=depth+1)
memoiz_list[money][coin_index] = problem_31_b(money, coin_index-1, depth=depth+1)+ \
problem_31_b(money-coin_list[coin_index],coin_index, depth=depth+1)
return memoiz_list[money][coin_index]

coin_list = [1,2,5,10,20,50,100,200]

for func in [problem_31_a, problem_31_b]:
glob_depth = 0
start = time.time()
memoiz_list = [[0,0,0,0,0,0,0,0] for i in range(201)]
print(func(200,7))
elapsed = time.time() - start
print("Result found in %f seconds - depth:%d" % (elapsed, glob_depth))

И действительно, мы получаем:

73682
Result found in 0.003184 seconds - depth:8
73682
Result found in 0.000919 seconds - depth:107

Ваш код, кажется быстрее, но и гораздо глубже в вызовы функций. Если вы превысили системные ограничения, можно было бы обновлять sys.setrecursionlimit. Однако, это может быть хорошей идеей, чтобы попробовать, чтобы исправить ваш код.

Вы могли бы написать решение, которое не выполняет каких-либо рекурсивных вызовов: вместо того, чтобы пытаться решить ваши проблемы, решая все меньше и меньше проблем и сохранение решения, как вы идете, вы могли бы просто обновить все проблемы от самых маленьких до самых больших нужно.

Например, можно написать:

def problem_31_c(money, unused):
nb_ways = [1] + [0] * money
for c in coin_list:
for v in range(money + 1 - c):
nb_ways[v + c] += nb_ways[v]
return nb_ways[-1]

Фактический комментарий код

Для обеих функций, это может быть хорошей идеей, чтобы сделать это очевидным, что мы имеем следующую картину:

if value_from_memoiz_list:
return value_from_memoiz_list
compute_value
store_value_in_memoiz_list
return value

В problem_31 например, мы видим, что ситуация приводит к результату, то вычисляется и возвращается без магазина в мемоизированную список. Кроме того, что дело может быть обработано с меньшим дублировать логику:

count = problem_31_b(money, coin_index-1)
coin_value = coin_list[coin_index]
if coin_value <= money:
count += problem_31_b(money-coin_value,coin_index)

Наконец, ваша стратегия повторного использования расчетной стоимости предполагает, что 0-это не существующий результат. Вы могли бы использовать None для этого. В вашем случае это не имеет значения, потому что никаких дорогостоящих вычислений приводит к 0, но это делает цель яснее код.

def problem_31_a(money, coin_index):
if coin_index <= 0:
return 1
money_rem = money
memo_value = memoiz_list[money][coin_index]
if memo_value is not None:
return memo_value
count = 0
while money_rem >= 0:
count += problem_31_a(money_rem, coin_index - 1)
money_rem -= coin_list[coin_index]
memoiz_list[money][coin_index] = count
return count

def problem_31_b(money, coin_index):
if coin_index < 0:
return 0
if coin_index == 0 or money == 0:
return 1
memo_value = memoiz_list[money][coin_index]
if memo_value is not None:
return memo_value
count = problem_31_b(money, coin_index-1)
coin_value = coin_list[coin_index]
if coin_value <= money:
count += problem_31_b(money-coin_value,coin_index)
memoiz_list[money][coin_index] = count
return count

Кроме того, вы можете использовать декоратор для реализации стратегии мемоизация.

Использование универсального декоратора от https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize вы могли бы написать:

coin_list = [1,2,5,10,20,50,100,200]

class memoized(object):
'''Decorator. Caches a function's return value each time it is called.
If called later with the same arguments, the cached value is returned
(not reevaluated).
'''
def __init__(self, func):
self.func = func
self.memoiz_list = [[None]*len(coin_list) for i in range(201)]
def __call__(self, money, coin_index):
try:
memo_value = self.memoiz_list[money][coin_index]
if memo_value is not None:
return memo_value
except IndexError:
pass
ret = self.func(money, coin_index)
try:
self.memoiz_list[money][coin_index] = ret
except IndexError:
pass
return ret
def __repr__(self):
'''Return the function's docstring.'''
return self.func.__doc__
def __get__(self, obj, objtype):
'''Support instance methods.'''
return functools.partial(self.__call__, obj)

@memoized
def problem_31_a(money, coin_index):
if coin_index <= 0:
return 1
money_rem = money
count = 0
while money_rem >= 0:
count += problem_31_a(money_rem, coin_index - 1)
money_rem -= coin_list[coin_index]
return count

@memoized
def problem_31_b(money, coin_index):
if coin_index < 0:
return 0
if coin_index == 0 or money == 0:
return 1
count = problem_31_b(money, coin_index-1)
coin_value = coin_list[coin_index]
if coin_value <= money:
count += problem_31_b(money-coin_value,coin_index)
return count

1
ответ дан 9 февраля 2018 в 02:02 Источник Поделиться