| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Помогите с АЛГОРИТМом
Igor M. © (2008-06-16 15:51:00)Голова кипит)
Пожалуйста, поделитесь мыслями, если у кого имеются.
Есть рейки одинаковой длины, допустим 2 метра.
Собираем рамки, т.е. четырехуголники)
В прогу я вбиваю ширину и высоту нужных рамок и в результате мне прога должна просчитать сколько нужно реек для этого и как оптимально их распилить на куски.
Или по другому если кто не понял):
Есть деревянные заготовки по 2 метра.
Есть массив нужных по длине отрезков.
Необходимо просчитать как оптимально разрезать заготовки.
Любую идею... плиз...
наблюдатель (2008-06-17 20:05:00) [1]http://alglib.sources.ru/combinatorial/backpack.php
http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&chapterid=60
http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&chapterid=59
Igor M. (2008-06-17 16:15:00) [2]я ещё и с математикой не дружу)
а собрался блин прогу писать...
вообщем СПАСИБО clickmaker ©, единственный дельное подсказал, тока я баран поздно понял..
тему можно закрывать..
начинаю писать прогу)
clickmaker (2008-06-17 16:08:00) [3]> 500+500+400+400+100 = 1.9 (10 сантиметров отходы)
500+500+400+400+300 - не влезло, берем след. по убыванию после 300
500+500+400+400+200 - влезло
Igor M. (2008-06-17 15:28:00) [4]ну я был написал чем вначале не понраивлся данный метод.
"
необходимо:
1. два отрезка по 200 два по 100
2. два отрезка по 200 два по 300
3. два отрезка по 300 два по 400
4. два отрезка по 500 два по 200
отрезаем:
500+500+400+400+100 = 1.9 (10 сантиметров отходы)
поэтому желательно как и написал:
первая заготовка - 5*200 + 2*300 + 400 = 2 метра
на данном мелком примере может и не так видно (один фиг две рейки тратим), но когда расчет идет по большому колличеству данных на данных моментах можно экономить..."
"
думал что есть что-то более точно..., но в результате clickmaker © огромное спасибо!, кажется лучше не придумаешь...
clickmaker (2008-06-17 15:10:00) [5]> [33] Igor M. (17.06.08 15:00)
а чем это отличается от [11]?
Igor M. (2008-06-17 15:00:00) [6]а если использовать алгоритм примерно такой:
упорядочиваем по возрастанию необходимые отрезки.
начинаем с "укладывания" больших отрезков на рейку, дополняя какие есть побольше двигаясь на сколько возможно в сторону уменьшения остатка. и так повторять покуда все не уложим.
как средний вариант пойдет?
я так понял математиков тута нету)
Igor M. (2008-06-17 09:28:00) [7]с правилом пока проблемы)
может у кого появились свежие мысли? )
хоть бредовых идей накидайте, а то вообще тупит что-то..
Anatoly Podgoretsky (2008-06-17 09:28:00) [8]> palva (17.06.2008 1:59:28) [28]
В метре все в порядке, если иметь особые метровые линейки.
palva (2008-06-17 06:41:00) [9]
> осталось придумать алгоритм перебора всех вариантов разбивки\разрезки
> реек..)
Сначала вам надо придумать правило записи при помощи переменных дельфи хотя бы отдельно взятого варианта разрезки.
Igor M. (2008-06-17 02:16:00) [10]palva © будем считать что забыл нолик дописать в размере одной рейки ))))
вообщем, как вариант, необходимо перебирать все возможные варианты разбивки и находить, где потребуется наименьшее колличество реек.
осталось придумать алгоритм перебора всех вариантов разбивки\разрезки реек..)
palva (2008-06-17 01:59:00) [11]ч
> разрез первой рейки на 10 отрезков по 100 см.
А сколько по-вашему в метре сантиметров, если из метровой рейки вы получаете 10 отрезков по 100 см?
Igor M. (2008-06-17 01:54:00) [12]я вот подумал, вероятно данный метод то же не годиться.
например, есть рейки по 1 метру.
необходимо иметь кускиЖ
- 10 штук по 100 см
- 10 штук по 600
- 10 штук по 300
поиском приближенных сумм я сразу выйду на разрез первой рейки на 10 отрезков по 100 см. ну и потом 10 реек потрачу на 600+300, из которых по 100 см. будет отходов. Отсюда явно видно, что лучший вариант - затрата 10 реек по 600+300+100.
Мда.. видать и правда простая на вид задача оборачивается совсем не простым алгоритмом..
Теперь меня терзают сомнения, - возможно ли вообще это реализовать..)))
palva (2008-06-17 01:46:00) [13]
> только непонял насчет " Если полный перебор вариантов невозможен"
> нам всё возможно! было бы желание)
Тогда какие проблемы? Перебирайте все суммы (их 2^n) и выбирайте ту из них, которая ближе всего к x.
Igor M. (2008-06-17 01:19:00) [14]palva © , вот и я об том же!
только непонял насчет " Если полный перебор вариантов невозможен"
нам всё возможно! было бы желание)
и "решение близкое к оптимальному" не понятно.
если есть числа, то паочему мы не может точно узнать какие элементы дают в сумме наиболее приближенное значение?
(если их несколько то выбираем любой)
по идее, применив рекурсию, я бы хоть как-то продвинулся в своей проблеме..
уже думал забросить это неблагодарное дело, но теперь даже интересно..
наверное прийдётся только ждать утренние свежие мысли...
Германн (2008-06-17 01:15:00) [15]
> Игорь Шевченко © (16.06.08 19:28) [12]
Дык и сейчас пишут. Riply так вообще пошла дальше. Фиг поймёшь чего она пишет! :)
> Igor M. (17.06.08 00:59) [19]
>
> з.ы.
> старость не радость.. что-то вообще голова не варит...
>
Сочувствую. Сам такой. Старость действительно не радость. Глаза, руки, ноги подводят постоянно. Особенно глаза.
Но голова вроде в порядке. :)
Igor M. (2008-06-17 01:14:00) [16]palva ©, подсказал бы лучше если знаешь)
Milk, я ж тебе говорил, что вначале поиронизируют чуток...
а ты за пример бан боишься)
palva (2008-06-17 01:12:00) [17]Хотя это не так уж и важно. Это тоже трудная задача из той же серии. Если полный перебор вариантов невозможен, то придется искать решение близкое к оптимальному.
palva (2008-06-17 01:03:00) [18]
> Igor M. (17.06.08 00:59) [19]
А все числа неотрицательные?
palva (2008-06-17 01:00:00) [19]Эвристика - это правдоподобные рассуждения, основанные на здравом смысле. В ветке их много.
Igor M. (2008-06-17 00:59:00) [20]я что-то и свой вариант не могу реализовать)
помогите, как найти сумму наиболее приближенную?
тоесть по-другому условие такое:
есть массив значений 0...n-1
необходимо найти элементы, сумма которых наиболее приближена к некоему значению X
з.ы.
старость не радость.. что-то вообще голова не варит...
| |
Страницы: 