[closed]задачка из ЕГЭ по информатике

Vadim69

Я тут готовлю одного балбеса к экзаменам по информатике и математике. В одном из вариантов ЕГЭ встретил такую задачу:

Задана длина полки – L. Имеется N<255 книг, толщина каждой из которых известна. Все они на полку не помещаются. Программа должна запрашивать L и толщины каждой из книг, и ответить на вопрос, какие из них (указать порядковый номер) следует поставить на полку, чтоб пустого места на полке оказалось как можно меньше. Допустимо вывести хотя бы один из возможных вариантов расстановки.

Вот.
Не подскажете, существует ли какой-нибудь подходящий алгоритм для таких задач?
Мое решение: перебирать сначала все комбинации из n/2 книг(получается C(n,n/2) комбинаций если среди них нет таких, которые заняли бы всю полку, то комбинации из 3n/4 книг, иначе, если среди них нет таких, которые бы влезли на полку, то из n/4 книг, иначе, если есть и такие, и такие, то оба варианта - и n/4, и 3n/4 - далее рекурсивно. Это отсекает лишние случаи, но в любом случае, уже при n=40 получаем что первым шагом перебираем C(40,20) книг(40!/(20!*20! - а это уже очень много и прога работает долго, не говоря уже о случае n=254. В любом случае, если придумать еще какие-нибудь отсечения, кардинально ситуацию это не изменит. Напрягает то, что задача из ЕГЭ, то есть по идее достаточно простая, а даже мой вариант таким не назовешь.
Запостил сюда, хотя можно и в стади... модераторам решать;)

Julie16

А задачи из ЕГЭ должны выполняться на компе? Имхо они там бумажки сдают... Или я не прав? Если прав - то простого перебора должно быть достаточно...

Vadim69

вроде иногда практическую часть принимают на компах(слышал что-то про такое). но он будет сдавать на бумажке. Мне сам факт существования в ЕГЭ такой задачи удивил. Сомневаюсь что нормальный школьник с легкостью сделает, пусть даже не оптимизированый, полный перебор с поиском оптимального варианта(тем более на бумажке, когда нет возможности отладить).

Helga87

Перебор не нужен.
Если решать методом динамического программирования, то решение потребует только двухмерного массива и двух циклов. Работает за O(L * количество книг) времени.
Если, конечно, толщины целые

sidsid

>Если, конечно, толщины целые
умножением на 10^X можно решить эту проблему

Vadim69

спасибо.
тему можно закрывать.