Алгоритм рекурсивного решения проблемы почтовой марки - PullRequest
Новая
       23

Алгоритм рекурсивного решения проблемы почтовой марки

0 голосов
/ 03 апреля 2019

Вот математическая проблема, известная как «проблема почтовой марки». Вам нужно положить определенное количество центов почтовых на конверте ( сумма ). На конверте есть место только для марок n (но не более).

Существует список доступных номиналов марок ( номиналов ). Вы можете использовать столько номиналов, сколько вам нужно. Цель состоит в том, чтобы получить необходимое количество с номиналом и ограниченное число марок n .

Например, для суммы = 12, n = 3 и номиналов = << 9 5 2 >> вы можете сделать это с 5+ 5 + 2. Но вы не могли сделать сумму = 17.

Как я могу решить это рекурсивно?

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

Был бы признателен алгоритм или небольшой намек на код в java.

Ответы [ 2 ]

0 голосов
/ 03 апреля 2019

Если все, что вам нужно, - это грубое решение, то будет работать что-то простое: 

Solve(amount, denoms[1...m], partial[1...n], pos, sum)
1. if sum = amount then print partial[1...n], pos - 1
2. if pos <= n then
3.    for i = 1 to m do
4.       partial[pos] = denoms[i]
5.       Solve(amount, denoms[1...m], partial[1...n], pos + 1, sum + denoms[i])
6.    partial[pos] = 0

Способ использовать это - сделать звонок Solve(amount, denoms[1...m], partial[1...n], 1, 0). Это напечатает все решения вместе с длиной каждого решения, с которым встречаются. Обратите внимание, что при этом будут распечатаны все перестановки каждого решения, поэтому он выполняет изрядное количество ненужной работы; кроме того, он продолжает рекурсию даже после превышения суммы. Обе эти проблемы могут быть исправлены с помощью нескольких дополнительных строк кода. Выполняйте рекурсивный вызов, например, только если текущая сумма меньше или равна сумме, и отслеживайте наименьшее использованное на данный момент наименование и используйте только обозначения. такого размера или меньше - но эти улучшения производительности не изменят производительность метода асимптотически значимым образом (то есть, они не делают алгоритм полиномиальным по времени). Действительно, эта проблема, вероятно, может быть довольно легко сведена к NP-полной задаче, и поэтому она, вероятно, не имеет доступного решения за полиномиальное время.

0 голосов
/ 03 апреля 2019

Это своего рода проблема с подмножеством сумм.

Рекурсивная функция должна обеспечивать: 

 stop condition: 
     when sum is zero and left count is zero - success
     when sum is zero and left count is non-zero - fail
     when sum is negative - fail
 traverse possible variants to solve simpler problem at the next recursion level:
     for every stamp value v check - 
       is it possible to make solution using value v and result of recursive call for count n-1
  (note: to avoid duplicate solutions, start traversal from the same stamp index, omitting lower indexes)
...