Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 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
1-1175676113
y0zh
2007-04-04 12:41
2007.06.03
Количество колонок в Excel (без OLE)


2-1179130182
Cavalera
2007-05-14 12:09
2007.06.03
Как в седьмом Делфи запустить Install Shield


2-1179340482
Slimer
2007-05-16 22:34
2007.06.03
Не завершается цикл while


6-1164279691
Warstone
2006-11-23 14:01
2007.06.03
Определения PID процесса, открывшего сокет


15-1178177317
Ega23
2007-05-03 11:28
2007.06.03
У жены сестра старшая двойню родила!!!





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский