Форум: "Прочее";
Текущий архив: 2007.06.03;
Скачать: [xml.tar.bz2];
ВнизАлгоритм оптимального расположения чисел Найти похожие ветки
← →
AXS4 © (2007-05-05 19:26) [0]В общем такая заморочка: Дано некое число (например 3000) и набор меньших чисел (например 400, 550, 700, 150, 770, 300, 1200, 420, 500, 1500, 270 и т. д.) Нужно распределить меньшие числа в цепочки чтобы их сумма либо была равна той самой 3000, либо минимализировать остаток
Пример цепочки 1500+1200+300 = 3000 (без остатка) и 700+500+550+400+420+270 = 2970 (остаток 30) и нераспределились 150 и 770
ВОПРОС - в чём логика алгоритма, как должен работать механизм распределения? Помогите пожалуйста...
PS Исполнять собираюсь на Delphi 7
← →
ArtemESC © (2007-05-05 19:40) [1]Для полного перебора много чисел?
← →
Leonid Troyanovsky © (2007-05-05 19:42) [2]
> AXS4 © (05.05.07 19:26)
> PS Исполнять собираюсь на Delphi 7
Все уже украдено до нас.
См. Excel addin (надстройка): Solver (Поиск решения) with help.
--
Regards, LVT.
← →
P (2007-05-05 20:12) [3]
> AXS4 © (05.05.07 19:26)
Найди любую книгу по дискретной математике и раздел "Жадные алгоритмы". Можно использовать рекурсию с альфа-бета отсечениями, но это сложнее, но по скорости сравнимо с жадными алгоритмами, а по эффективности близко к полному перебору.
← →
TUser © (2007-05-05 20:19) [4]задача np-полная, так что оптимального решения кроме как перебором все равно не найти
ищи по словам дискретная задача о лукошке :), она на твою похожа
← →
TUser © (2007-05-05 20:45) [5]Макконел. Основы современных алгоритмов.
Там, кажется, обсуждается твоя задача, могу прислать, проси по почте/аське.
← →
MOA © (2007-05-05 21:00) [6]Она же "задача об укладке ранца" ;).
← →
ferr © (2007-05-05 21:01) [7]> ищи по словам дискретная задача о лукошке :), она на твою
> похожа
Тогда уж "задача о рюкзаке" ("knapsack problem").
← →
AXS4 © (2007-05-05 23:11) [8]
> ArtemESC © (05.05.07 19:40) [1]
> Для полного перебора много чисел?
Может быть до 20-30 чисел при том что они могут совпадать
← →
ferr © (2007-05-05 23:12) [9]оценка O(2^N)
для 30 чисел самое оно ;-)
← →
AXS4 © (2007-05-05 23:16) [10]Возможно я не так силён в программировании, как хотелось бы, но вы уж извините меня, я мало чего понял из того что тут написали. Нельзя ли более понятно и последовательно объяснить принцип "рюкзака" иль "лукошка" .
← →
AXS4 © (2007-05-05 23:17) [11]
> ferr © (05.05.07 23:12) [9]
> оценка O(2^N)
> для 30 чисел самое оно ;-)
??? В примере можно?
← →
ferr © (2007-05-05 23:43) [12]http://www.tspu.tula.ru/ivt/old_site/umr/ealg/docs/doc07/doc07.htm
http://ru.wikipedia.org/wiki/Задача_о_рюкзаке
и.т.д.
← →
AXS4 © (2007-05-05 23:47) [13]Я прочитал что было понятно о жадном алгоритме и если я правильно понял, то я должен взять самое большое число затем из оставшихся самое большое сложить их и проверить не превышен ли предел (3000) если нет то далее так же, если да то пробую меньшее, так? Но тогда вторая цепочка (770+700+550+500+420 = 2940) не такая оптимальная как моя, полученная опытным путём (700+500+550+400+420+270 = 2970)... Или я не всё понял?
Может я неправильно выразился и мне нужен не алгоритм а более или менее примерный код в делфи? Мне главное уловить все нюанся механизма....
Заранее спасибо.
← →
ferr © (2007-05-05 23:55) [14]нет, тебе нужен не жадный.
← →
ferr © (2007-05-05 23:56) [15]тебе надо перебрать все варианты. это можно сделать отобразив все возможные варианты на числа от 0 до (2^n - 1).
← →
palva © (2007-05-05 23:59) [16]Не очень понятно, что значит минимизировать остаток, если остатков несколько. Кроме того, если у нас много небольших чисел, составляющих в сумме 4500, то их придется разместить в двух цепочках. Если мы будем минимизировать остаток в первой цепочке, то остаток во второй цепочке увеличится. Следуя вашей логике "Но тогда вторая цепочка не такая оптимальная как моя." нам не следует минимизировать остаток в первой цепочке, поскольку это вызовет ухудшение ситуации со второй цепочкой.
Корректно задача может быть поставлена так: разместить числа по цепочкам и обеспечить минимальное количество цепочек. Ваша же постановка задачи просто непонятна. Что надо минимизировать неизвестно.
← →
AXS4 © (2007-05-06 00:02) [17]
> тебе надо перебрать все варианты. это можно сделать отобразив
> все возможные варианты на числа от 0 до (2^n - 1).
Ага, я тоже так подумал. Но только не знаю как все варианты сложения реализовать.... :-( Можно "от 0 до (2^n - 1)." более понятно разъяснить? Желательно с примером, как я объяснял свою проблемку...
← →
AXS4 © (2007-05-06 00:04) [18]
> разместить числа по цепочкам и обеспечить минимальное количество
> цепочек
Совершенно верно! Я извиняюсь если что перемудрил...
← →
ferr © (2007-05-06 00:10) [19]> Желательно с примером, как я объяснял свою проблемку...
Если надо минимизировать количество цепочек как только что выяснилось то это уже не задача о рюкзаке.
← →
AXS4 © (2007-05-06 00:13) [20]
> Если надо минимизировать количество цепочек как только что
> выяснилось то это уже не задача о рюкзаке.
А это проще? Очень надеюсь что вы мне поможете с этим...
← →
palva © (2007-05-06 00:19) [21]В свое время я пытался запихнуть, к примеру, 100 файлов на 5 дискет. Я знал, что 4-х дискет заведомо не хватит из соображения суммарной длины файлов, а 5 должно хватить. Я распихивал файлы по разным дискетам. Сначала пытался разместить большие файлы, потом поменьше. Иногда все получалось, но иногда я сталкивался с ситуацией, когда у меня осталось два файла и ни один из них не помещался ни на одну из дискет. Вот только тогда я начинал минимизировать остатки, то есть пытался записать на дискету какой-то из оставшихся файлов, предварительно удалив с нее один или несколько уже записанных файлов меньшего размера, добиваясь, чтобы остаток на этой дискете был минимален. Файлы меньшего размера уже можно было поместить на остальные дискеты. А бывало, что и нельзя. Тогда я ругался и добавлял еще одну дискету. Хорошего алгоритма я так и не придумал. Наверно кроме полного перебора здесь ничего не придумаешь.
← →
ferr © (2007-05-06 00:21) [22]> Наверно кроме полного перебора здесь ничего не придумаешь.
Жадная стратегия тут хоть как не пройдёт. А оценка тут похуже рюкзака будет..
← →
ferr © (2007-05-06 00:23) [23]Но может автор всё-таки задачу объяснит а? Какую блин функцию минимизировать надо совсем непонятно.. Если как в примере с дискеттами то это одно, а вот причём здесь тогда "и нераспределились 150 и 770"?
← →
AXS4 © (2007-05-06 00:24) [24]Ладно, пойдём другим путём - где взять инфу по полному перебору написанную понятным языком?
← →
AXS4 © (2007-05-06 00:32) [25]
> а вот причём здесь тогда "и нераспределились 150 и 770"?
Точнее распределились, но уже в третью цепочку...
← →
ferr © (2007-05-06 00:32) [26]Ну допустим Шень. Программирование в теоремах и задачах вроде бы называется. Валяется бесплатно в интернете, в пдф. Вроде бы даже на сайте МЦНМО..
← →
TUser © (2007-05-06 10:33) [27]http://monkey.belozersky.msu.ru/~evgeniy/lib/THEOR.HTM
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2007.06.03;
Скачать: [xml.tar.bz2];
Память: 0.51 MB
Время: 0.047 c