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

Проблема с задачей...
Автор Morgan_HackProg, 12 лет назад, По-русски

Столкнулся с такой проблемой: Дан массив целых чисел (не больше 50 елементов). Надо сказать, не является ли любое из чисел суммой нескольких других из этого массива. Не знаю как это сделать эфективно.

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

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

Не знаю как это сделать эфективно.

  1. Какая асимптотика тебе нужна?
  2. Напиши ограничения чисел.
  3. Откуда задача
→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1007&rid=50e34132eff8a

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      На таких ограничениях рюкзак проще всего, а если бы числа были произвольными, meet-in-the-middle можно применять.

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Можно по-подробнее с meet-in-the-middle?

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

          Делим элементы на две равные части, генерируем в каждой из частей суммы всех подмножеств. Все суммы вместе с соответствующими битмасками сохраняем в два массива, по одному для каждой части. После этого перебираем все элементы и идем двумя указателями по массивам, пытаясь набрать нужную сумму. При этом в том массиве, откуда родом рассматриваемый элемент, не надо учитывать те подмножества, куда он входит. O(n·20.5n) должно зайти.

          И да, я считаю, что для зеленых как рюкзак, так и meet-in-the-middle слишком сложно, лучше сначала научиться безошибочно решать халяву и приобрести олимпиадное мышление. Это гарантированно принесет фиолетовый цвет, и только потом уже можно начинать изучать алгоритмы с пользой для себя. Вот так.

          → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Рюкзак не смог написать(решение пытается минимальным путем дойти). Вот рекурсия (не знаю пройдет ли по времени).

      UPD: В решении с рекурсии размер массива a лучше увеличить до 110.

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

При небольших ограничениях можно сложить рюкзак, параллельно считая количество чисел в каждом элементе рюкзака. Потом пройти по рюкзаку, смотря только на те элементы, которые составлены более, чем из 1 числа, и проверять, есть ли число в последовательности, равное элементу рюкзака. Соответственно проставлять в последовательности true. Потом проверить, все ли числа из последовательности помечены, как true. Вот тут читать про рюкзак.

→ Ответить