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

Автор difask, история, 9 лет назад, По-русски

Всем привет!

Помогите решить задачу. Думал много над ней с друзьями, но решения на полный бал так и придумали.

Дано N<50 досок с известными длинами a[i]<10000. Их можно разрезать на любое количество досок. Есть доски которые нужно получить. Их M<1024, b[i]<128. Нужно найти максимальное количество досок, которое можно получить.

Example:
Input:
4
30 40 50 25
10
15 16 17 18 19 20 21 25 24 30
Output:
7
Explanation:
15 + 16 + 17 -> 50 (разрезаем 50 на 15, 16, 17, 50-15-16-17=2)
18 + 19 -> 40
20 -> 30
21 -> 25

Спасибо!

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

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

А где можно сдать?

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

А нет места, где бы отправить?

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

Я не верю, что у этой задачи есть решение, которое проходит любой набор тестов в разумное время. На Тимусе давно лежит почти такая же задача, просто в ней есть гарантия что разрез на все мелкие доски существует и надо его найти. В ней слабые тесты и проходит перебор, но у нее есть усложненная версия с серьезными тестами, которую на сегодняшний день всего четыре человека смогли запихать.

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

    Если в указанной задаче на тимусе требуется, чтобы каждый ряд кораблей был полностью заполнен, то разве задачи будут одинаковыми?

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

      А, действительно, условие на тимусе кривое какое-то. Я думаю что задача все равно слишком похожа на многомерный рюкзак, чтобы быть разумно решаемой.

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

        Представьте себе такую задачу.

        Пусть x — количество денег. Пусть y[i] — стоимости товаров. Нужно найти максимальное количество товаров, которые можно купить за не больше, чем x денег.

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

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

        Я тут это все пишу не просто, чтобы пристать с нелепыми замечаниями к Вам.

        Мне действительно кажется, что задача у автора сильно проще, чем та, которая на тимусе.

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

        Извините, понял, что сведение очевидно. Туплю. Спасибо!