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

Question

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

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

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

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

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

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

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

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

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

Answer 1

Позволять 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