Блог пользователя Kickman

Автор Kickman, история, 8 лет назад, перевод, По-русски

Дается число N(<= 10^4), A(|A| <= 10^4) и N чисел, каждое из которых по модулю меньше 10^4, и их сумма не превосходит 10^4. Требуется расставить плюсы и минусы между числами, чтобы сумма получившегося выражения была наиболее близка к A.

  • Проголосовать: нравится
  • -37
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был переведен пользователем Kickman (оригинальная версия, переведенная версия, сравнить).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Рюкзак. Возможно, есть решение быстрее, но у меня в свое время зашла динама за О(N*SUM) c bitset-ами.