Уведомления

Группа в Telegram: присоединиться

#1 Янв. 2, 2011 23:04:38

Enchantner
От:
Зарегистрирован: 2009-02-11
Сообщения: 442
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача о сдаче

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

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

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

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

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



Отредактировано (Янв. 2, 2011 23:34:57)

Офлайн

#2 Янв. 3, 2011 00:12:18

Zubchick
От:
Зарегистрирован: 2009-07-08
Сообщения: 613
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача о сдаче

эта задача решалась в sicp

UPD: Правда через глубокую рекурсию



Отредактировано (Янв. 3, 2011 00:13:07)

Офлайн

#3 Янв. 3, 2011 00:19:08

Enchantner
От:
Зарегистрирован: 2009-02-11
Сообщения: 442
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача о сдаче

Zubchick
в лиспе все так :) Сейчас он уже, к сожалению, почти не котируется… Поэтому и интересно на питоне



Офлайн

#4 Янв. 3, 2011 01:16:43

sp3
От:
Зарегистрирован: 2010-01-12
Сообщения: 405
Репутация: +  18  -
Профиль   Отправить e-mail  

Задача о сдаче

наверно не в тему

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



Офлайн

#5 Янв. 3, 2011 09:17:05

PooH
От:
Зарегистрирован: 2006-12-05
Сообщения: 1948
Репутация: +  72  -
Профиль   Отправить e-mail  

Задача о сдаче

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



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

Офлайн

#6 Янв. 3, 2011 09:57:33

PooH
От:
Зарегистрирован: 2006-12-05
Сообщения: 1948
Репутация: +  72  -
Профиль   Отправить e-mail  

Задача о сдаче

В 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! :)



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

Офлайн

#7 Янв. 3, 2011 11:13:41

Enchantner
От:
Зарегистрирован: 2009-02-11
Сообщения: 442
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача о сдаче

PooH
Жадный алгоритм тут подходит только когда начальный набор номиналов это позволяет, а он может запросто быть любым. А вот за второй пример спасибо, покопаю. И мне, кстати, нужно не только минимальное число монет, но и вывесли, какие именно монеты. Я так понимаю, что в случае количества комбинаций это задача просто на комбинаторику.



Отредактировано (Янв. 3, 2011 11:16:57)

Офлайн

#8 Дек. 23, 2020 09:36:13

elddd
Зарегистрирован: 2020-12-23
Сообщения: 4
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача о сдаче

Здраствуйте!
у меня есть алгоритм:
например, дается 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)

Офлайн

#9 Янв. 11, 2021 18:27:45

Master_Sergius
Зарегистрирован: 2013-09-12
Сообщения: 252
Репутация: +  7  -
Профиль   Отправить e-mail  

Задача о сдаче

Не разбирал написанные коды выше, поэтому, возможно, повторю чье-то решение. Я напишу лишь алгоритм, который узнал в студенческие годы:

Пытаемся сложить сумму от 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). И так далее, надеюсь алгоритм понятен.



———————————————————————————
Мой блог о семействе *nix: http://nixtravelling.blogspot.com/

Отредактировано Master_Sergius (Янв. 11, 2021 18:28:40)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version