DjangoBB LoFi version

Начало » Python для экспертов » Задача о сдаче

Enchantner

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

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

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

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

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

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

Zubchick

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

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

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

Enchantner

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

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

sp3

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

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

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

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

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

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

PooH

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

В 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

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

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

elddd

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

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

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

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

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