В зависимости от величины данного числа, может быть быстрее использовать динамическое c программирование. Если tot - данное число, а arr - массив возможных слагаемых, то приведенный ниже метод имеет вычислительную сложность O(tot*arr.size).
Код
def find_summands(arr, tot)
return [] if tot.zero?
arr.each_with_object([{tot=>nil}]) do |n,a|
h = a.last.each_key.with_object({}) do |t,h|
return soln(arr,a.drop(1),n) if t==n
h[t] = 0
h[t-n] = n
end
a << h
end
nil
end
def soln(arr,a,n)
t = n
a.reverse.each_with_object([n]) do |h,b|
m = h[t]
b << m
t += m
end.reverse.tap { |a| (arr.size-a.size).times { a << 0 } }
end
Примеры
arr = [1, 1, 3, 4, 5, 7]
find_summands(arr, 8)
#=> [1, 0, 3, 4, 0, 0]
find_summands(arr, 11)
#=> [1, 1, 0, 4, 5, 0]
find_summands(arr, 21)
#=> [1, 1, 3, 4, 5, 7]
find_summands(arr, 22)
#=> nil
find_summands([1, -2, 3, 4, 5, 7], 6)
#=> [1, -2, 3, 4, 0, 0]
Каждый ноль в возвращенном массиве указывает, что соответствующий элемент в arr не используется в суммировании.
Объяснение
Предположим:
arr = [4, 2, 6, 3, 5, 1]
tot = 13
затем
find_summands(arr, tot)
#=> [4, 0, 6, 3, 0, 0]
Когда решение получено, вызывается soln, чтобы привести его в более полезную форму:
soln(arr, a.drop(1), n)
Здесь arr такое же, как указано выше, и
n #=> 3
a #=> [
{13=>nil}, # for tot
{13=>0, 9=>4}, # for arr[0] => 4
{13=>0, 11=>2, 9=>0, 7=>2}, # for arr[1] => 2
{13=>0, 7=>0, 11=>0, 5=>6, 9=>0, 3=>6, 1=>6} # for arr[2] => 6
]
n равно значению последнего использованного слагаемого от arr слева направо.
При рассмотрении arr[0] #=> 4 оставшаяся сумма для суммирования равна 13, ключ a[0] #=> {13=>nil}. Есть две возможности, 4 является слагаемым или нет. Это приводит к ха sh
a[1]
#=> {13-0=>0, 13-4=>4}
# { 13=>0, 9=>4}
, где ключами являются оставшаяся сумма, которая будет суммироваться, и значение равно 4, если 4 является слагаемым, и равно нулю, если это не так.
Теперь рассмотрим arr[1] #=> 2. Мы смотрим на ключи a[1], чтобы увидеть, какие возможные оставшиеся суммы могут быть после использования 4 или нет. (13 и 9). Для каждого из них мы рассматриваем использование или не использование 2. Это приводит к тому, что га sh
a[2]
#=> {13-0=>0, 13-2=>2, 9-0=>0, 9-2=>2}
# { 13=>0, 11=>2, 9=>0, 7=>2}
7=>2 может быть прочитано, если 2 (значение) является слагаемым, есть выбор использования arr[0] или нет, что приводит к в оставшуюся сумму, которая будет суммирована после включения 2, будет 7.
Далее рассмотрим arr[2] #=> 6. Мы смотрим на клавиши a[2], чтобы увидеть, какие могут быть возможные оставшиеся суммы после использования 4 и 6 или нет. (13, 11, 9 и 7). Для каждого из них мы рассматриваем использование или не использование 6. Поэтому мы теперь создаем га sh
a[3]
#=> {13-0=>0, 13-6=>6, 11-0=>0, 11-6=>6, 9-0=>0, 9-6=>6, 7-0=>0, 7-6=>6}
# { 13=>0, 7=>6, 11=>0, 5=>6, 9=>0, 3=>6, 7=>0, 1=>6}
# { 13=>0, 11=>0, 5=>6, 9=>0, 3=>6, 7=>0, 1=>6}
Можно прочитать пару 11=>0, "если 6 не является слагаемым, есть выбор использования или не использования arr[0] #=> 4 и arr[2] #=> 2, что приводит к суммированию оставшейся суммы после 6, равной 11 ".
Обратите внимание, что пара ключ-значение 7=>6 была перезаписана на 7=>0, когда не использовалось 6, считалось с оставшейся суммой 7. Мы ищем только одно решение, поэтому не имеет значения, как мы доберемся до оставшейся суммы 7 после того, как будут рассмотрены первые три элемента arr. Эти столкновения имеют тенденцию к увеличению, когда мы движемся слева направо в arr, поэтому число состояний, которые мы должны отслеживать, значительно сокращается, потому что мы можем "выбросить" так много их.
Наконец (как выясняется) мы рассмотрим arr[3] #=> 3. Мы смотрим на клавиши a[3], чтобы увидеть возможные оставшиеся суммы после того, как 4, 2 и 6 были использованы или нет (13, 11, 5, 9, 3, 7 и 1). Для каждого из них мы рассматриваем использование или не использование 3. Мы зашли так далеко, создав ха sh a[4]:
{13=>0, 10=>3, 11=>0, 8=>3, 5=>0, 2=>3, 9=>0, 6=>3, 3=>0, 0=>3}
Поскольку последняя пара ключ-значение имеет нулевой ключ, мы знаем, что нашли решение.
Давайте построим решение. Поскольку значение 0 равно 3, 3 является слагаемым. (Мы бы нашли решение раньше, если бы значение было равно нулю.) Теперь мы работаем в обратном направлении. Поскольку используется 3, оставшееся количество до 3 составляет 0+3 #=> 3. Мы находим, что a[3][3] #=> 6, что означает 6, также является слагаемым. Остаток баланса до использования 6 составлял 3+6 #=> 9, поэтому мы вычисляем a[2][9] #=> 0, что говорит нам о том, что 2 не является слагаемым. Наконец, a[1][9-0] #=> 4 показывает, что 4 также является слагаемым. Отсюда и решение
[4, 0, 6, 3, 0, 0]