Всем привет!
Помогите решить задачу. Думал много над ней с друзьями, но решения на полный бал так и придумали.
Дано 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
Спасибо!
А где можно сдать?
А нет места, где бы отправить?
Я не верю, что у этой задачи есть решение, которое проходит любой набор тестов в разумное время. На Тимусе давно лежит почти такая же задача, просто в ней есть гарантия что разрез на все мелкие доски существует и надо его найти. В ней слабые тесты и проходит перебор, но у нее есть усложненная версия с серьезными тестами, которую на сегодняшний день всего четыре человека смогли запихать.
Если в указанной задаче на тимусе требуется, чтобы каждый ряд кораблей был полностью заполнен, то разве задачи будут одинаковыми?
А, действительно, условие на тимусе кривое какое-то. Я думаю что задача все равно слишком похожа на многомерный рюкзак, чтобы быть разумно решаемой.
Представьте себе такую задачу.
Пусть x — количество денег. Пусть y[i] — стоимости товаров. Нужно найти максимальное количество товаров, которые можно купить за не больше, чем x денег.
Вот это, насколько я понимаю, условие одномерного варианта той задачи, которая стоит перед автором поста. Разве она похожа на рюкзак? По-моему, решается жадностью при любых ограничениях на веса.
Я тут это все пишу не просто, чтобы пристать с нелепыми замечаниями к Вам.
Мне действительно кажется, что задача у автора сильно проще, чем та, которая на тимусе.
Извините, понял, что сведение очевидно. Туплю. Спасибо!