Задачка

← →
Alx2 (2002-07-23 13:38) [0]

Недавно забор городил и возник сабж: :)
Есть несколько пролетов забора, в которые вставляются трубы, для того чтобы на них крепить ограждение.
И есть несколько труб, которые надо распилить под пролеты так, чтобы количество обрезков свести к минимуму.
Длины пролетов: P1,..,Pn
Длины труб: T1,..,Tm. Конечно, длина трубы должна превышать длину пролета (хотя и необязательно).
Так вот: нужно посчитать какую трубу и где пилить, чтобы суммарную длину отходов свести к минимуму.

← →
al2002 (2002-07-23 15:54) [1]

Сначала начни с коротких труб для коротких пролётов.
Или наоборот.

>
Разобрался с кодировками для html2hlp?

← →
Alx2 (2002-07-23 16:13) [2]

>al2002 © (23.07.02 15:54)
Пришлось конвертер в промежуточный формат написать (просто кодировал русские символы). После этого html2hlp запускал, а потом в rtf-никах перекодировал в hex-кодировку wordовскую (иначе, с русскими символами компилятор helpов не справлялся).
Все настроил, погонял на мелких примерах - работает.
Натравил на основную задачу (3000 html-файлов) - конвертер html2hlp умер по недопустимой операции и посоветовал отправить такой-то файл разработчикам.

>Сначала начни с коротких труб для коротких пролётов.
Не панацея, однако :)

← →
Alx2 (2002-07-23 16:17) [3]

>al2002 © (23.07.02 15:54)
Контрпример:

Набор труб: 600 600 600 800 760 525
Набор пролетов: 322 322 280 280 285 285 287 287 288 288 289 289

Оптимальная раскладка:
600= 280 285 (отход 35)
600= 285 287 (отход 28)
600= 287 288 (отход 25)
800= 322 322 (отход 156)
760= 288 289 (отход 183)
525= 289 (остаток 236)
Всего отходов: 663

При этом, естественно, какому-то пролету труб не хватило.

← →
al2002 (2002-07-23 16:38) [4]

А пролёты – это константы?

← →
al2002 (2002-07-23 16:44) [5]

>Пришлось конвертер в промежуточный формат написать (просто
>кодировал русские символы). После этого html2hlp запускал, а
>потом в rtf-никах перекодировал в hex-кодировку wordовскую
>(иначе, с русскими символами компилятор helpов не справлялся).
Что-то жутко накручено. ХТМЛ в KOI-8 у тебя?

>Все настроил, погонял на мелких примерах - работает.
>Натравил на основную задачу (3000 html-файлов) - конвертер
>html2hlp умер по недопустимой операции и посоветовал отправить
>такой-то файл разработчикам.
А у меня щас работает .... 3902 из 17288. Пока не умер. )))

>Сначала начни с коротких труб для коротких пролётов.
Не панацея, однако :)

Ну, и ещё вариант ))))))
Добавь пролётов из того, что будет отходами. Только крепче будет.

← →
al2002 (2002-07-23 16:45) [6]

Насчёт умер.
А ты флажочки снял с Minor Warnings & Table Warnings?

← →
Alx2 (2002-07-23 16:49) [7]

>al2002 © (23.07.02 16:45)
Кажется, не снимал. Действительно, глюк может там и сидеть :)
>Что-то жутко накручено. ХТМЛ в KOI-8 у тебя?
Windows 1251
>А пролёты – это константы?
Ага

← →
Виктор Щербаков (2002-07-23 17:04) [8]

to Alx2 ©
Хорошая задачка!
Лучшая из попадавшихся за последнее время.

← →
al2002 (2002-07-23 17:04) [9]

>>А пролёты – это константы?
>Ага.
Тогда будут отходы... будут... я сказал...

← →
al2002 (2002-07-23 17:09) [10]

>Windows 1251
8-[+]
Тогда в чём грабли? У меня HTML2HLP как раз и работает с этой кодировкой.
В опциях шрифт поменяй.

← →
Igorek (2002-07-23 23:22) [11]

Задачку можно простым перебором решить. Да и вариантов не очень много придется перебрать, как мне кажеться. Будет время - напишу алгоритм.

← →
Alx2 (2002-07-24 08:11) [12]

>Igorek © (23.07.02 23:22)
>Задачку можно простым перебором решить.
Конечно, но тормоза обеспечены, если не подумать.
>Да и вариантов не очень много придется перебрать,
>как мне кажеться
???
А это уже интересно!

← →
Desdechado (2002-07-24 11:03) [13]

может, проще сварить трубы, а потом пилить?
и отходов не будет :)

← →
Виктор Щербаков (2002-07-24 11:06) [14]

← →
Alx2 (2002-07-24 11:07) [15]

>может, проще сварить трубы, а потом пилить?
Нет ни сварочного аппарата, ни сварщика :(

← →
Desdechado (2002-07-24 11:28) [16]

2 Виктор Щербаков © (24.07.02 11:06)
отходы не столько стоят. а вот если из-за них не хватит нормальных труб, то за них придется платить больше

2 Alx2 © (24.07.02 11:07)
тогда делай нерегулярный забор с разными пролетами. такого ни у кого не будет :)

← →
Alx2 (2002-07-24 11:35) [17]

>Desdechado © (24.07.02 11:28)
Пролеты уже есть. И уже нерегулярные: разлет до 20 см.

PS
Собственно, эта задачка из разряда "размять мозги". Программульку написал, но времени уходит много на расчет несмотря на использование метода "ветвей и границ".

← →
Алгоритмист (2002-07-24 12:02) [18]

Классическая задача оптимизации из курса "Принятие решений" !
Решается аналогично транспортной задаче или задаче о коммивояжере...

← →
Alx2 (2002-07-24 12:17) [19]

>Алгоритмист (24.07.02 12:02)
>Решается аналогично транспортной задаче
>или задаче о коммивояжере...
По-моему в транспортной задаче нет NP - полноты, в отличие от задачи коммивояжера.

Задачка Найти похожие ветки