Найти - Пользователи
Полная версия: Задача о сдаче
Начало » Python для экспертов » Задача о сдаче
1
Enchantner
Ковыряю динамическое программирование, стало интересно, как подобную задачу грамотно решить динамикой на питоне.

Суть такова: на входе сумма и список номиналов имеющихся монет, задача - выдать эту сумму минимальным числом монет.

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

Как бы это грамотно и красиво реализовать на Python? Хотелось бы врубиться и в динамику, и в то, как вообще такие задачи решаются на питоне…

def __upd__(): нашел вот эту ссылку http://www.bryceboe.com/2009/11/04/dynamic-programming-%E2%80%93-coin-change-problem-in-python/
попробую раскурить. Но вообще такой класс задач в последнее время все больше меня интересует.
Zubchick
эта задача решалась в sicp

UPD: Правда через глубокую рекурсию
Enchantner
Zubchick
в лиспе все так :) Сейчас он уже, к сожалению, почти не котируется… Поэтому и интересно на питоне
sp3
наверно не в тему
baks = 1113.1
nominals = [2,1,5,10,50]

nominals.sort()
nominals.reverse()

print baks, '$ =>'

for k in nominals:
d = baks//k
baks = baks -d*k
print k,'$ :',int(d)

print 'nerazmeneno:', baks
PooH
sp3
наверно не в тему
Очень даже в тему, жадный алгоритм тут прекрасно подходит. Просто Enchantner задачу неудачно выбрал.
PooH
В sicp задача стоит - найти количество всех способов размена суммы данным набором монет. Возьмем оттуда код на схеме и переведем на питон. Добавим только счетчик вызовов.
def first_denomination(kinds):
return {1: 1, 2: 5, 3: 10, 4: 25, 5:50}[kinds]

call_count = 0

def cc(amount, kinds):
global call_count
call_count += 1
if not amount:
return 1
elif amount < 0 or not kinds:
return 0
else:
return cc(amount, kinds-1) + cc(amount-first_denomination(kinds) ,kinds)

def count_change(amount):
return cc(amount, 5)

print 'result', count_change(100)
print 'call count', call_count
result 292
call count 15499
Собственно, это уже динамическое программирование - задача сведена к подзадачам меньшей размерности. Для скорости сохраняют решения промежуточных подзадач. Возьмем код отсюда memoize
class memoized(object):
"""Decorator that caches a function's return value each time it is called.
If called later with the same arguments, the cached value is returned, and
not re-evaluated.
"""
def __init__(self, func):
self.func = func
self.cache = {}
def __call__(self, *args):
try:
return self.cache[args]
except KeyError:
value = self.func(*args)
self.cache[args] = value
return value
except TypeError:
# uncachable -- for instance, passing a list as an argument.
# Better to not cache than to blow up entirely.
return self.func(*args)
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)

def first_denomination(kinds):
return {1: 1, 2: 5, 3: 10, 4: 25, 5:50}[kinds]

call_count = 0

@memoized
def cc(amount, kinds):
global call_count
call_count += 1
if not amount:
return 1
elif amount < 0 or not kinds:
return 0
else:
return cc(amount, kinds-1) + cc(amount-first_denomination(kinds) ,kinds)

def count_change(amount):
return cc(amount, 5)

print 'result', count_change(100)
print 'call count', call_count
result 292
call count 250
Voila! :)
Enchantner
PooH
Жадный алгоритм тут подходит только когда начальный набор номиналов это позволяет, а он может запросто быть любым. А вот за второй пример спасибо, покопаю. И мне, кстати, нужно не только минимальное число монет, но и вывесли, какие именно монеты. Я так понимаю, что в случае количества комбинаций это задача просто на комбинаторику.
elddd
Здраствуйте!
у меня есть алгоритм:
например, дается 2, 3, 5
программа выведет 3, 1, 0, 2
первое число это минимальное количество монет
остальное это какие монеты были использованы
def coins_min(coins, weight, length):
result =
for i in range(1, weight + 1):
minimum = i
specific =
j = 0
for coin in coins:
if i - coin >= 0 and result + 1 <= minimum:
minimum = result + 1
specific = copy.deepcopy(result)
specific += 1
j += 1
result.append((minimum, specific))
print(result)
Master_Sergius
Не разбирал написанные коды выше, поэтому, возможно, повторю чье-то решение. Я напишу лишь алгоритм, который узнал в студенческие годы:

Пытаемся сложить сумму от 0 до S из имеющихся номиналов. К примеру, у нас есть номиналы 1, 2, 5:
Сумма для нуля будет, что-то вроде
 s[0] = 0
. Потом следующие суммы как можно получить с каждым номиналом? Проверить, можно ли доложить данную монетку. То есть,
 s[N] = s[N-nominal]+ nominal
. Выбираем наименьшее из всех доступных, в случае с (1,2,5):
 s[N] = min(S[N-1] + 1, S[N-2] + 1, S[N-5] + 1)
То есть,
 S[1] = 1
,
 S[2] = min(S[1] +1, S[0]+1, S[-3]+1)
, поскольку
 S[-3]
не существует, то его не рассматриваем, значит
 S[2] = 1
(положить лишь одну монетку 2 меньше чем две монетки по 1). И так далее, надеюсь алгоритм понятен.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB