Решение для динамического программирования для варианта обмена монет - PullRequest
Новая
       46

Решение для динамического программирования для варианта обмена монет

0 голосов
/ 06 мая 2018

Я практикую динамическое программирование. Я концентрируюсь на следующем варианте проблемы обмена монет:

Пусть S = [1, 2, 6, 12, 24, 48, 60] будет постоянным набором целых номиналов монет. Пусть n будет положительным целым количеством денег, которое можно получить с помощью монет в S. Рассмотрим двух человек A и B. Во сколько разных способов я могу разделить n между людьми A и B так, чтобы каждый человек получил одинаковое количество монет (независимо от фактической суммы денег, которую получает каждый)?

Пример

n = 6 может быть разделен на 4 различных способа на человека:

  1. Человек A получает {2, 2}, а человек B получает {1, 1}.
  2. Человек A получает {2, 1}, а человек B получает {2, 1}.
  3. Человек A получает {1, 1}, а человек B получает {2, 2}.
  4. Человек A получает {1, 1, 1}, а человек B получает {1, 1, 1}.

Обратите внимание, что каждый путь не является лишним на человека, т. Е. Мы не считаем {2, 1} и {1, 2} двумя разными способами.

Предыдущее исследование

Я изучал очень похожие проблемы DP, такие как проблема обмена монет и проблема разбиения. На самом деле, на этом сайте есть вопросы, относящиеся почти к той же проблеме:

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

Например, эта рекурсия: 

def f(n, coins):
  if n < 0:
    return 0

  if n == 0:
    return 1

  return sum([f(n - coin, coins) for coin in coins])

Заманчиво, но не работает, потому что при исполнении: 

# => f(6, [1, 2, 6]) # 14

Вот пример прогона для S' = {1, 2, 6} и n = 6, чтобы помочь мне прояснить схему (могут быть ошибки):

Example for S' = {1, 2, 6} and n = 6

Ответы [ 2 ]

0 голосов
/ 15 мая 2018

Вот таблица реализации и небольшая проработка красивого ответа algrid . Это дает ответ на f(500, [1, 2, 6, 12, 24, 48, 60]) примерно за 2 секунды.

Простое объявление C(n, k, S) = sum(C(n - s_i, k - 1, S[i:])) означает добавление всех способов получить текущую сумму, n с использованием k монет. Затем, если мы разделим n на все способы, которыми он может быть разбит на две части, мы можем просто добавить все способы, которыми каждая из этих частей может быть изготовлена ​​из того же числа, k, из монет.

Красота фиксирования подмножества монет, которое мы выбираем, в уменьшающемся списке означает, что любая произвольная комбинация монет будет учитываться только один раз - она ​​будет учитываться при расчете, где крайняя левая монета в комбинации является первой монетой в наше уменьшающееся подмножество (при условии, что мы упорядочиваем их таким же образом). Например, произвольное подмножество [6, 24, 48], взятое из [1, 2, 6, 12, 24, 48, 60], будет учитываться только при суммировании для подмножества [6, 12, 24, 48, 60], так как следующее подмножество [12, 24, 48, 60] не будет включать 6 и предыдущее подмножество [2, 6, 12, 24, 48, 60] имеет хотя бы одну 2 монету.

Код Python (см. здесь ; подтвердите здесь ): 

import time

def f(n, coins):
  t0 = time.time()

  min_coins = min(coins)

  m = [[[0] * len(coins) for k in xrange(n / min_coins + 1)] for _n in xrange(n + 1)]

  # Initialize base case
  for i in xrange(len(coins)):
    m[0][0][i] = 1

  for i in xrange(len(coins)):
    for _i in xrange(i + 1):
      for _n in xrange(coins[_i], n + 1):
        for k in xrange(1, _n / min_coins + 1):
          m[_n][k][i] += m[_n - coins[_i]][k - 1][_i]

  result = 0

  for a in xrange(1, n + 1):
    b = n - a

    for k in xrange(1, n / min_coins + 1):
      result = result + m[a][k][len(coins) - 1] * m[b][k][len(coins) - 1]

  total_time = time.time() - t0

  return (result, total_time)

print f(500, [1, 2, 6, 12, 24, 48, 60])
0 голосов
/ 08 мая 2018

Вот что вы можете попробовать:

Пусть C(n, k, S) будет числом различных представлений суммы n, использующих несколько k монет из S.

Тогда C(n, k, S) = sum(C(n - s_i, k - 1, S[i:])) Суммирование для каждого s_i с S. S[i:] означает все элементы от S, начиная с i -го элемента до конца - это необходимо для предотвращения повторных комбинаций.

Начальные условия: C(0, 0, _) = 1 и C(n, k, _) = 0, если n < 0 или k < 0 или n > 0 и k < 1.

Число, которое вы хотите вычислить:

R = sum(C(i, k, S) * C(n - i, k, S)) для i = 1..n-1, k = 1..min(i, n-i)/Smin, где Smin - наименьшая номинал монеты из S.

Значение min(i, n-i)/Smin представляет максимальное количество монет, которое возможно при разбиении данной суммы. Например, если сумма n = 20 и i = 8 (1-й человек получает 8 долларов, 2-й получает 12 долларов) и минимальный номинал монет составляет 2 доллара, максимально возможное количество монет 8/2 = 4. Вы не можете получить 8 долларов с >4 монетами.

...