Как решить задачу расстановки арифметических знаков между числами для получения другого числа?

Question

[keddad]

Даны N целых чисел, задача - расставить между ними знаки + и - для получения числа S с сохранением исходной последовательности чисел в выражении, или доказательства невозможности получения такого S. Например, если числа - [7, 3, 9] и S = 13, то ответ, удовлетворяющий задаче = 7-3+9=13

Как можно реализовать такой алгоритм?

• 
  
• Если единственное решение - тупой перебор, то как сделать премутацию для получения всех возможных вариантов расстановки знаков?
  
• Если есть более эффективное решение (умный перебор, или что то вкуснее), то как его реализовать?
  
• Как выглядел бы алгоритм без сохранения исходной последовательности чисел?
  

Comments

[keddad]

Было бы интересно увидеть идеи псевдокодом, или на чем то C/Python подобном

[Шохрух Шаймардонов]

keddad, кодлм не подскажу, но если без сторонних библиотек, то вам перебор нужен. Тут чисто задача на комбинаторику. Таблицу истинности вспомните как на уроках информатики делали. Если вам нужно использовать только + и -, то собственно у вас возможных вариантов будет 2^(N-1). Основание зависит от количества операторов. Дальше дело за брутфорсом.

Answer 1

[Сергей Соколов]

Полным перебором можно считать каждый знак битом: 0 это плюс, 1 минус. Получается, надо перебрать все числа от 0 до 2^(n-1) и их двоичная запись кодирует знаки.

Для оптимизации можно сначала проверить некоотрые крайние условия:

• например, «все плюсы» должны быть >= S. Чтобы сразу отсечь проверку вариантов получения 1E9 из всего 1E6 единиц. Эта же проверка имеет смысл в процессе перебора, для оценки, дотянутся ли оставшиеся цифры до оставшейся до S суммы
  
• Проверить четность - из четного числа нечетных не получить нечетное.
  
• Подумать, что делать с одинаковыми числами, как-то отсечь их зеркальные комбинации.
  
• Ещё подумать
  

Comments

[keddad]

Вполне годное решение, но это олимпиадная задача, такое решение просто недостаточно оптимально для нее, мне кажется. Я практически уверен в том, что тут есть возможность превратить все в динамику, но не могу сформулировать мысль :(

[Сергей Соколов]

keddad, проверка на четность отбросит половину вариантов )

[Сергей Соколов]

мне кажется, надо копать математику. Тут дерево вариантов удваивается с каждым числом. На каждом шаге, наверное, можно оценивать признак все оставшиеся с плюсом >= расстояние до S, чтобы отсекать крупные ветки.

Answer 2

[Rsa97]

Если у вас только два знака и ставиться они могут только между числами, то просто генерируете все числа от 0 до 2^N-1 и принимаете, например, бит 0 за минус, а бит 1 за плюс.