|
v7: Нужен алгоритм поиска значений | ☑ | ||
---|---|---|---|---|
0
vova1122
29.09.13
✎
17:47
|
Такая задача: Есть некий набор разных чисел. И есть ещё одно число, назовем его например "НужнаяСумма".
Так нужно среди этого набора чисел найти сумму некоторых чисел которые были бы наиболее близки к НужнойСумме (в идеале равной нужнойСумме). Может кто-то уже делал подобное, или хотя-бы подскажите алгоритм как это реализовать? |
|||
1
МихаилМ
29.09.13
✎
17:49
|
в поиск. было раз 20.
|
|||
2
vova1122
29.09.13
✎
17:51
|
(1) хоть примерно по каким критериям искать
|
|||
3
МихаилМ
29.09.13
✎
17:52
|
||||
4
МихаилМ
29.09.13
✎
17:53
|
||||
5
Эмбеддер
29.09.13
✎
19:21
|
создаем еще одну колонку "разность", записываем туда в цикле проходя по строкам разницу (по модулю), сортируем по возрастанию. первая строка - требуемая
|
|||
6
vova1122
29.09.13
✎
21:19
|
(5) совсем не то....
|
|||
7
Torquader
29.09.13
✎
21:51
|
Строгий подход к задаче требует построения дерева сумм.
Сначала мы перебираем все записи в таблице - если находим равную, то берём её, если нет, то суммы больше необходимой просто выбрасываем. Далее строим таблицу из пар сумм оставшихся после предыдущего шага - если нашли - вот и решение, если нет, то больше нужного отбрасываем. Потом строим таблицу трёх ... и так далее. Когда при построении очередной таблицы мы не получили в ней ни одного элемента - перебор заканчивается. Максимальное значение полученной суммы будет наилучшим приближением снизу (если нужно приближение сверху, то при отбрасывании слагаемых мы также сохраняем самый меньший результат). Метод будет очень и очень долгим, но гарантированно даст результат. Если хочется быстро - то берём массив. Если сумма массива меньше нужной, то добавляем в массив случайный элемент из таблицы, если больше, то удаляем любой элемент из массива - если совпало, то получаем ответ. Также полезно хранить "треки" массива при максимальной снизу и минимальной сверху сумме. Метод запускает на ограниченное время, если оно закончилось, а результат не найден, то выбираем один из приближённых. |
|||
8
GANR
29.09.13
✎
21:55
|
(0) Имхо, задача наитривиальнейшая...
|
|||
9
GANR
29.09.13
✎
21:58
|
(0) А хотя стоп-стоп...
Это, наверное, задачка комбинаторики - нужно перебрать возможные сочетания чисел C(n, k), при этом, вероятно, меняя k от 1 до n. Сначала подумал, что надо одно наиболее близкое число найти - тогда нет, не так уж и тривиально... http://ru.wikipedia.org/wiki/Сочетание |
|||
10
victor79
29.09.13
✎
23:47
|
я делал подобное через перебор через рекурсию. Других алгоритмов не придумал. Только там количество переборов пропорциональна факториальной функции. И если в искомое число вмещается больше ~13 значений из перебираемых - то количество перебора зашкаливает. И тогда нужен не прямой перебор, а случайный - что будет посложнее в понимании.
|
|||
11
victor79
29.09.13
✎
23:56
|
вот навскидку пример полного перебора. Но не тестил, так что могут быть глюки - разбирайся.
Перем спРяд, спРез, спЛучшийРез; Перем мин_ост; Процедура рекурсия(нач, ост) Если ост < мин_ост Тогда спРез.Выгрузить(спЛучшийРез); мин_ост = ост; КонецЕсли; для н = нач по спРяд.РазмерСписка() Цикл дли = спРяд.ПолучитьЗначение(н); Если дли > ост Тогда продолжить; КонецЕсли; спРез.ДобавитьЗначение(дли); рекурсия(н+1, ост-дли); спРез.УдалитьЗначение(спРез.РазмерСписка()); КонецЦикла; КонецПроцедуры Функция Поиск(спЗначения, ИскомаяДлина) спРез = СоздатьОбъект("СписокЗначений"); спЛучшийРез = СоздатьОбъект("СписокЗначений"); спРяд = спЗначения; мин_ост = ИскомаяДлина; рекурсия(1, ИскомаяДлина); возврат спЛучшийРез; КонецФункции |
|||
12
victor79
29.09.13
✎
23:58
|
забыл, там если спРяд предварительно отсортировать по возрастанию, тогда при условии дли>ост можно делать прервать.
|
|||
13
Злопчинский
30.09.13
✎
01:12
|
NS как-то выкладывал сырцы, я взял, допилил - вроде работает - юзается у меня для подбора объема палет.
. можно еще вот ту посмотреть, не идеал, но фунциклует с горем пополам http://infostart.ru/public/14526/ |
|||
14
vova1122
30.09.13
✎
11:48
|
(11) Полным перебором реально дождаться максимум до 25 значений (перебор будет длится целый день. Для большего числа значений нужно что-то другое......
|
|||
15
Mikeware
30.09.13
✎
11:50
|
Если просто сумма чсел - задачка тривиальная. а если допускается целочисленный множитель у числа - тут уже надо звать NS
|
|||
16
vova1122
30.09.13
✎
11:56
|
(15) просто сумма чисел (каждое число может быть только один раз). Может подкинете идею как это сделать не полным перебором
|
|||
17
GANR
30.09.13
✎
15:04
|
(16) может здесь есть что-нибудь подходящее http://algolist.manual.ru/maths/combinat/sequential.php ?
|
|||
18
NikVars
30.09.13
✎
15:09
|
(0) Математически это частный случай предела
Определение и основные свойства предела последовательности http://hijos.ru/izuchenie-matematiki/mat-analiz-10-klass/36-opredelenie-i-osnovnye-svojstva-predela-posledovatelnosti/ |
|||
19
Калиостро
30.09.13
✎
15:25
|
(0) Ты задачу озвучь немного подробней. Абсолютная точность здесь очень затратная задача. Если надо делать списание товара под сумму розничной выручки - нужна одна точность. А для расчета заполнения заданий на развозку другая. В любом случае надо сделать на 1с грубую прикидку, а подгонку делать вручную.
|
|||
20
Злопчинский
30.09.13
✎
17:00
|
(19) списание товара под сумму розничной выручки я делал - упомянуто в (13) - там даже без особой математики все получается более-менее нормально
|
|||
21
vova1122
30.09.13
✎
18:45
|
(19) Задача. Есть список выписанных документов (расходные накладные) для бюджетных организаций. Но у них нет денег чтобы оплатить эти накладные.
Они предложили такой вариант: так как мы платим также некии отчисления в бюджет то они предлагают списать долг по взаимозачету. Но нужно набрать документы (расходные накладные) на суму нашего обезательства перед бюджетом. |
|||
22
ADirks
30.09.13
✎
19:09
|
Твоя задача - это задача о рюкзаке (ранце)
wiki:Задача_о_ранце ну и там ещё дофига ссылок никогда не занимался, ничего дельного не скажу |
|||
23
Злопчинский
30.09.13
✎
19:12
|
"задача о рюкзаке".
у меня работает алгоритм: из коробок/блоков/штук определенного объема (у тебя = реализации) набрать объем палеты (у тебя обязательства перед бюджетом). У меня не совсем так - большая накладаная делится на палеты указанного объема с максимально близкой набивкой палеты под указанный объем. Чем больше в наличии мелких коробок - тем лучше подбирается. |
|||
24
Злопчинский
30.09.13
✎
19:14
|
задачу в (23) - как писал выше - реализовывал по алгоритму? который выкладывал NS - допиливал, вносил частности.
. а если тупо - то в (21) нормально сработает простой алгоритм, который я тоже указывал выше - подбор продаж под сумму Z-отчета |
|||
25
Мимохожий Однако
30.09.13
✎
19:18
|
Когда нет денег, то проще оплачивать маленькие по сумме накладные. Список долгов по накладным будет быстрее укорачиваться. Однако есть вариант попроще - остаток переплаченных денег зафиксировать как частичный платеж за следующую по списку накладную.
|
|||
26
Злопчинский
30.09.13
✎
19:21
|
вот пример подбора под нужную цифру:
http://screencast.com/t/tY24IeX71 . как видно - палеты в итоге получаются с малйо погрешностью = заказанному числу 1.44. |
|||
27
Torquader
01.10.13
✎
00:18
|
Если значение повторяется только один раз, то можно рассмотреть множество значений, тогда каждое значение суммы можно сопоставить двоичному числу, у которого единица стоит в позиции вошедшего элемента, а ноль - не вошедшего. Перебрав все такие "числа" мы выполним полный перебор, но это достаточно долго, если "число" получается более 32 двоичных цифр.
Когда значений много, то помогает случайный выбор: Берём массив наших чисел, из которых будет выполняться перебор. У массива выделяется граница, то есть положение области суммирования, все числа левее (меньше) границы входят в сумму, а числа правее (больше по номеру) - нет. Если сумма меньше нужной, то добавляем в массив случайно выбранный элемент выше или равный границы - при этом, если элемент не на границе, то меняем его с граничным местами, после чего границу сдвигаем вверх. Если сумма больше, то удаляем случайный элемент слева от границы - для этого выбираем элемент, и если не попали на самый ближний к границе, то меняем выбранный с ним местами. После этого сдвигаем границу влево. Таким образом получаем случайный процесс с плавающей границей, для каждого случая рассматриваем разницу с искомым числом - если она меньше, чем была в прошлый запомненный раз, то просто запоминаем массив. Данный случайный процесс хорошо даёт ответ, если нужно сделать выборку из более ста чисел, когда простой перебор займёт очень длительное время (только представление массива - это 2 в сотой степени). |
|||
28
vova1122
08.10.13
✎
20:46
|
Всё-же частично решил для себя эту проблему. Сделал через полный перебор, но работает на порядок (а может и больше) чем вариант полного перебора изложенном в (11).
Конечно для выборки из большого количества чисел будет долго но для 50-80 чисел можно применять. Для примера выборка из 30 чисел (найти максимум 10 складовых) будет крутится примерно 4 минуты. |
|||
29
Михаил Козлов
08.10.13
✎
21:22
|
Пусть {ai} - множество чисел.
Составим производящую функцию сумм: F(x) = (1+x^a1)*((1+x^a2)*...*(1+x^an). Начнем перемножать множители, приводя подобные члены. В результате получим F(x) = СУММА(Bk*x^k). Тогда Bk - число решений уравнения СУММА(ai*xi)=k (xi=0 или 1), т.е. число возможных наборов чисел из {ai}, дающих в сумме k. Например, пусть {ai} = {1,2,3.4} Тогда F(x) = 1+x+x^2+2*x^3+2*x^4+2*x^5+2*x^6+2*x^7+x^8++x^9++x^10. Т.е. для 0,1,2,8,9,10 - 1 решение, для 3,4,5,6,7 - два. Трудоемкость такого метода - сумма всех ai. По опыту для чисел в диапазоне 1-20 для нескольких сотен переменных решается (даже в 1С!) за приемлимое время (для случайных а от 1 до 20 и количества чисел = 100 время около секунды. Для случайных от 1 до 50 и количество чисел = 200 - секунд 20). |
|||
30
Злопчинский
08.10.13
✎
21:23
|
(28) бред какой-то, 30 чисел, 4 минуты...у меня на заявках под 800 строк (то есть 800 чисел), отрабатывает практически без задержек...
|
|||
31
vova1122
08.10.13
✎
22:44
|
(30) тогда может все-таки поделитесь своим решением?
|
|||
32
Михаил Козлов
09.10.13
✎
10:24
|
(30) Скорее всего, каким-нибудь вариантом "жадного" алгоритма.
|
|||
33
vova1122
09.10.13
✎
13:24
|
(13) Этот вариант не подходит. Так как даже есть точный вариант эта обработка его не найдёт (проверял).
|
|||
34
Михаил Козлов
11.10.13
✎
13:14
|
(33) Тогда закладывайтесь на неявный перебор или как в (29). К слову: в (29) я привел данные по времени для несколько более трудоемкой задачи (можно было использовать одно число несколько раз).
Могу на досуге сделать (29), но в 8-ке. Если нужно - пишите (мыло в профиле). Сразу ограничение: все числа целые. |
|||
35
Эмбеддер
11.10.13
✎
13:49
|
(28) перебор сейчас на 1С или другой ЯП?
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |