Консультации Портала - Консультация #124562

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 124562

24.02.2008, 00:47

0.00 руб.

0 1 1

Компьютеры Программирование

Здравствуйте, уважаемые эксперты!

Помогите составить алгоритм или подскажите направление или идею реализации следующего:

На листе бумаги формата А4, портретной ориентации нужно расположить печатные формы нескольких накладных так, чтобы пустое поле внизу листа было минимальным, а сами накладные не разрывались краем листа на две части (есть аналогичная настройка в текстовых редакторах - "Не разрывать абзац" и "Запрет висячих строк"). Минимальное количество строк накладной фиксировано и состоит из заголовка (номер накладной, дата, клиент, строка заголовка таблицы = 3 строки), подвала таблицы (строка Итого плюс разделитель накладной = 2 строки) и одна строка табличной части.

Что для меня не сложно и практически готово: получить общее количество накладных из журнала за указанный период (например, день), прочитать их в память, составить линейный массив из количества строк: <code>
Элемент[i] = Заголовок+Подвал+СтрокНакладной</code> (т.е. 3+2+КоличествоСтрокНакладной).

Что меня затрудняет: получившийся массив перекомпоновать так, чтобы результирующие накладные заполняли лист наиболее рационально. Т.е. из получившегося множества элементов второго массива составить суммы, которые были бы меньше (количества строк в листе), но не больше (количество строк в листе минус пять строк на заголовки накладной).

Наглядный пример:

В листе вмещается 60 строк с учетом технологических отступов принтера сверху и снизу.
Минимальная длина накладной - 6 строк (Заголовок 3 строки + 1 строка таблицы + Подвал 1 строка + строка-разделитель накладных). Допускается, чтобы разделитель печатался на последней строке листа.
10 накладных за день с количество строк: 3, 7, 4, 5, 6, 6, 3, 1, 1, 1.
После обработки накладных, получился массив длин печатных форм этих накладных: 3+5=8, 7+5=12, 4+5=9, 5+5=10, 6+5=11, 6+5=11, 3+5=8, 1+5=6, 1+5=6, 1+5=6.
Теперь из элементов массива 8, 12, 9, 10, 11, 11, 8, 6, 6, 6 нужно составить суммы, не более 60 (строк в листе) и не менее 55 (60-длина зголовка и подвала накладной). Послежнюю страницу в не берём в счет.
Должно получиться:
1-й лист: 12+10+11+11+8+8 = 60 строк (лиист заполнен рационально)
2-й лист: 8+9+8+6+6+6 = 43 строки (примерно 75% использования).

Аналогичный алгоритм я видел в системе Базис-мебельщик для раскроя листов фанеры (ДСП) на детали для сборки, но там используется двумерный массив.

Спасибо за внимание.
С уважением, Владимир.

Обсуждение

давно

Megaloman

Модератор
137394
1850

24.02.2008, 13:04

общий

это ответ

Здравствуйте, Владимир Лазурко [Vladal]!
Ваш пример я или недопонял (разъясните, пожалуйста в форуме), или не совсем корректен- Вы привели массив из 10 элементов 8, 12, 9, 10, 11, 11, 8, 6, 6, 6, а суммы составляете из 12 элементов, 12+10+11+11+8+8; 8+9+8+6+6+6. Да и задача, наверное, в таких жестких условиях (не более 60 (строк в листе) и не менее 55) в принципе не решаема для любых данных. В частности, может и повезти. Вообще, задача оптимизации - это вопрос к математикам, если сами этим аппаратом не владеем.
Могу предложить примитивный алгоритм (я тоже мат аппаратом минимаксных задач оптимизации не владею):

1. Пересортируем массив по убыванию. Для Ваших данных это
12 11 11 10 9 8 8 6 6 6
Я назову его исходным.

2. Сопоставим исходному массиву такой-же по длине логический массив, все элементы которого =true
Назову этот массив индикаторным.

3. Перепишем исходный массив в массив для печати (Назову его выходным) следующим образом:

Цикл (1) до тех пор пока все элементы индикаторного массива не станут false

В переменной, для определенности, L, контролируем длину сформированной для печати страницы (L<=60).
*Начальное значение L=0

Цикл (2)- вложенный в (1)- по всем элементам исходного массива.
Просматриваем исходный массив от первого (максимального) до последнего (минимального) элемента. В переменной, для определенности, L, контролируем длину сформированной для печати страницы (L<=60).

Если элемент индикаторного массива =false (т. е. эта накладная еще не записана для печати), то:

Если L+элемент исходного массива <= 60 переписываем элемент исходного на первое незаполненное место выходного массива. Делаем L=L+элемент исходного массива. Элемент индикаторного массива делаем равным true.

В результате этого процесса для Вашего примера получим выходной массив:
12 11 11 10 9 6 8 8 6 6
Т е на 1 листе 59 строк, на последнем - 28

Итак, я предложил простой алгоритм, идея которого состоит в том, что я стараюсь последовательно вбивать в лист максимально длинные накладные из числа необработанных.
Для написания конкретного кода мне маловато конкретики, а что-то писать в предположениях не хочется.

Очевидный недостаток: на последних листах скорее всего собирутся все самые короткие накладные.

Об авторе:
Понеже не словес красных бог слушает, но дел наших хощет

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.