Форум: "Потрепаться";
Текущий архив: 2002.08.19;
Скачать: [xml.tar.bz2];
Вниз
Задачка Найти похожие ветки
← →
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]Desdechado © (24.07.02 11:03)
Сварщику платить придется. Это может оказаться больше стоимости отходов :)
← →
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 - полноты, в отличие от задачи коммивояжера.
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.08.19;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.007 c
