Алгоритм оптимального расположения чисел

← →
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]

> Желательно с примером, как я объяснял свою проблемку...

Если надо минимизировать количество цепочек как только что выяснилось то это уже не задача о рюкзаке.

> Если надо минимизировать количество цепочек как только что
> выяснилось то это уже не задача о рюкзаке.

А это проще? Очень надеюсь что вы мне поможете с этим...

В свое время я пытался запихнуть, к примеру, 100 файлов на 5 дискет. Я знал, что 4-х дискет заведомо не хватит из соображения суммарной длины файлов, а 5 должно хватить. Я распихивал файлы по разным дискетам. Сначала пытался разместить большие файлы, потом поменьше. Иногда все получалось, но иногда я сталкивался с ситуацией, когда у меня осталось два файла и ни один из них не помещался ни на одну из дискет. Вот только тогда я начинал минимизировать остатки, то есть пытался записать на дискету какой-то из оставшихся файлов, предварительно удалив с нее один или несколько уже записанных файлов меньшего размера, добиваясь, чтобы остаток на этой дискете был минимален. Файлы меньшего размера уже можно было поместить на остальные дискеты. А бывало, что и нельзя. Тогда я ругался и добавлял еще одну дискету. Хорошего алгоритма я так и не придумал. Наверно кроме полного перебора здесь ничего не придумаешь.

> Наверно кроме полного перебора здесь ничего не придумаешь.

Жадная стратегия тут хоть как не пройдёт. А оценка тут похуже рюкзака будет..

Но может автор всё-таки задачу объяснит а? Какую блин функцию минимизировать надо совсем непонятно.. Если как в примере с дискеттами то это одно, а вот причём здесь тогда "и нераспределились 150 и 770"?

Ладно, пойдём другим путём - где взять инфу по полному перебору написанную понятным языком?

> а вот причём здесь тогда "и нераспределились 150 и 770"?

Точнее распределились, но уже в третью цепочку...

Ну допустим Шень. Программирование в теоремах и задачах вроде бы называется. Валяется бесплатно в интернете, в пдф. Вроде бы даже на сайте МЦНМО..

http://monkey.belozersky.msu.ru/~evgeniy/lib/THEOR.HTM

Алгоритм оптимального расположения чисел Найти похожие ветки