Оптимизация обмена монет

Я пытаюсь решить эту проблему:

Предположим, у меня есть набор из n монет {a_1, a2, ..., a_n}. Монета со значением 1 всегда будет появляться. Какое минимальное количество монет мне нужно, чтобы достичь M?

Ограничения:

  • 1 ≤ n ≤ 25
  • 1 ≤ m ≤ 10^6
  • 1 ≤ a_i ≤ 100

Хорошо, я знаю, что это проблема внесения изменений. Я пытался решить эту проблему, используя поиск в ширину, динамическое программирование и жадность (что неверно, поскольку не всегда дает лучшее решение). Однако я получаю сообщение о превышении лимита времени (3 секунды).

Поэтому мне интересно, есть ли оптимизация для этой проблемы. Описание и ограничения привлекли мое внимание, но я не знаю, как использовать это в свою пользу:

  • Монета со значением 1 всегда будет появляться.
  • 1 ≤ a_i ≤ 100

Я видел в википедии, что эту проблему также можно решить с помощью «Динамического программирования с вероятностным деревом свертки». Но я ничего не мог понять.

Вы можете помочь мне? Эту проблему можно найти здесь: http://goo.gl/nzQJem


dynamic-programming breadth-first-search greedy coin-change
person skide    schedule 13.09.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Пусть a_n будет самой крупной монетой. Используйте эти две подсказки:

  • результат >= ceil(M/a_n),
  • конфигурация результата имеет много a_n's.

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

Что-то вроде: пусть R({a_1, ..., a_n}, M) будет функцией, которая возвращает результат для данной задачи. Чем R можно реализовать:

num_a_n = floor(M/a_n)
best_r = num_a_n + R({a_1, ..., a_(n-1)}, M-a_n*num_a_n)
while num_a_n > 0:
  num_a_n = num_a_n - 1
  # Check is it possible at all to get better result
  if num_a_n + ceil(M-a_n*num_a_n / a_(n-1) ) >= best_r:
     return best_r
  next_r = num_a_n + R({a_1, ..., a_(n-1)}, M-a_n*num_a_n)
  if next_r < best_r:
    best_r = next_r
return best_r
person Ante    schedule 14.09.2014
comment
Спасибо за ваш ответ. Я пытался реализовать это, в некоторых случаях это быстро, а в других - медленно. Затем я попытался поставить мемозацию, но она стала O(n*m). - person skide; 19.09.2014
comment
Я думаю, что мемоизацию можно сделать за O(n * min(M, a_na_{n-1})). Ниже M-a_na_{n-1} искать не нужно. - person Ante; 19.09.2014
comment
очень умное решение! Теперь у меня есть АС. Большое спасибо! - person skide; 20.09.2014