Почитал все темы на мисте, но так и не определился с оптимальным решением.
Задача: Есть большой набор произвольных целых чисел (1 млн чисел). Так же существует менее большой набор числовых промежутков (100000).
Необходимо использовать максимальную сумму числе для подбора всех промежутков. Лучшее решение является сумма промежутков на максимальную сумму подобранных чисел
Пример:
1,2,3,4,5,6,7,8,9, 10
промежутки: 3-5, 6-8, 55 - 57
Плохое решение:
промежуток 3-5 можно подобрать значениями 3,2
А промежуток 6-8 значениями 7,1
Плохое решение: 55 - 57 подобраны все числа.
Лучшее решение: 55 - 57 подобраны (10, 9,7,6,4,3,2,1)
3-5 числа: 5
6-8 числа: 8

(0) ни... не понял!

Так.... попытка номер два ))

Существует пул целых чисел, они произвольные. Всего таких чисел почти 1 млн.

Также существует пул числовых интервалов. Таких промежутков 100 тыщ.

Необходимо подобрать сумму из чисел первого ряда, так что бы они попали в интервалы из второго ряда.
При подборе надо исходить из того, что не должно остаться интервалов без подобранных чисел. Лучшим решением является минимальное значение Сумма(интервалов) - Сумма(подобранных чисел).

Сейчас алгоритм работает так:
цикл по всем интервалам и подбирается максимальное число их рада 1. Дальше в цикле повторяем, пока не пробежим всеми числами. Но есть мысль что существует более оптимальное решение.

Задача собрать НЕСКОЛЬКО рюкзаков, как можно плотнее

(4) Собрать все рюкзаки как можно плотнее )

(5) оптимальность решения по общей сумме идет или по количеству полностью загруженных рюкзаков?

(2) надо наполнить рюкзаки минимальным кол-вом чисел?

т.е. чем плохо решение для промежутка 3-5 суммой чисел 3+2=5 ? в отличие от одной 5 ?

по общей сумме рюкзаков за минусом подобранных вещей
Пример:
Рюкзак1 вместимость 100 подобранных вещей на 90
Рюкзак2 вместимость 40 подобранных вещей на 26
Рюкзак3 вместимость 65 подобранных вещей на 3
итого (100+40+65) - (90+26+3). Чем меньше эта разница тем лучше.

(7) в данном случае решение одинаково хороши.

смекнул, что лучше брать не интервалы, а максимальную вместимость рюкзаков, так будет оптимальнее. Но в алгоритме (3) сейчас используются именно интервалы, а именно если подобранная сумма входит в интервал, то останавливаем подбор.

Рюкзаки - интервалы пересекаться могут?

Задача всегда имеет решение? Т.е. может числе не хватить? Или можно числа по нескольку раз юзать ))

(0) Верно ли понял, что сумма чисел, отнесенных к одному интервалу должна быть в границах интервала?
Тогда не понятно, как сумма чисел (10,9,7,6,4,3,2,1) попадает в интервал 55-57.
(8) Т.к. сумма длин интервалов от решения не зависит, ее в критерии можно опустить.

(11) да

(10) да лучше заполнять максимальными числами по верхнему пределу и если не получилось то оставить такой рюкзак (незаполненный) на последок

после заполнения всех рюкзаков по верхнему пределу перейти к заполнению оставленных на (макс.вместимость-1) и т.д.

(12) Да , тоже дошел до этого )

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

(16) А чем хуже вариант с рюкзаками оставшимися пустыми? Ну все влезло в предыдущие.

(16) а это уже отдельная задача перераспределения содержимого рюкзаков

(16) по одному макс.доступному числу в каждый рюкзак, а далее (14)

(17) Задача о себестоимости, не может быть продукции без себестоимости, что то на нее должно пойти.

Учитывая размерности, даже жадный алгоритм будет давать порядка 1 000 000 * 100 000 операций (100 ярдов). Тут, мне кажется, не до оптимальности.

новый вид учета - рюкзаковый. рауз отдыхает. не говоря уж о партионном :)

(19) Будет ли данный способ оптимальным и задействовать максимальное сумму чисел?

(20) можно спросить? а нафига? т.е. чем Вам реальная себестоимость не устроила?

(24) Что есть реальная себестоимость? Ее не существует это миф.

(25) э?

(18) Вот мы заполним максимально рюкзаки по очереди, то Вы уверены, что при этом задействуется максимальная сумма чисел? Я что то сомневаюсь

(25)(26)+ т.е. я не спорю что реальную можно иногда высчитать только после продажи товара и выплаты зп (всех долгов по связанным контрагентам)

но почему низзя то?

(26) Себестоимость по партиям сильно отличается от РАУЗ, а играясь ном группами, так же можно себестоимость изменить до не узнаваемости.
Но ни одна из этих методик не решает задачу максимализировать себестоимость.

(28) Это уже не себестоимость, а итоговая маржа.
Или себестоимость = продали - прибыль?

(28) Ушли в другую тему. Нет такого понятия как реальная себестоимость, дайте ей определение )

(23) Нет конечно. Оптимальный способ гарантировано будет найден за О(1000000^100000), ну т.е. полный перебор. Все остальное - только лишь приближение (иногда совпадающее с оптимумом)

(32) А различные методики ветвей, генетический алгоритм, тут не помогут?

(30) нет просто себестоимость это все затраты, в т.ч. дополнительные кроме стоимости товара

"за скоко купили" +  "транспортные" + "мелкая часть от аренды склада" + "мелкая часть от выплаченной зп" + ... = себестоимость

(33) не зная ограничения на числа и какие есть точно решения нет

(33) Почему нет? Нужно исследовать вопрос. Наверняка не скажу. Эти алгоритмы (и не только эти) ищут приближенное решение, иногда с заданной точностью, для задач подобной сложности. Какой алгоритм в данном случае будем лучшим - сложно сказать. Я бы исходил все-таки прежде всего из ограниченных вычилительных мощностей)

(34) А вот можно часть материалов оставить в производстве и не распределять на продукцию. Таким образов всегда остается пул, которым можно добивать себестоимость будущих продукций.

Поэтому сейчас изначально распределяются косвенные затраты, а потом уже прямые (материальные)

А вашего ГБ налоговая за подобную методологию за .опу не схватит?)) Как-то уж больно далеко от классических вариантов и на мухлеж смахивает

А зачем вообще тогда себестоимость по единице продукции считать? Считайте по группам, или вообще котоловым способом

(38) Любой расчет себестоимости это мухлеж.

(40) Зачем Вам тогда интервалы? Просто набивайте рюкзаки, скажем, жадным алгоритмом (ничто другое по Вашим размерностям не прокатит).

(41) Жадный сейчас и работает... но была надежда на поиск более оптимального

(42) А жадный чем плох? Проверить-то его не можете.
Кстати, сколько времени он у Вас молотит?

(8) Я один не понял, что математику обмануть невозможно?
(100+40+65) - (90+26+3) = 205 - 119
Заполнить 205 затратами на 119 - куда не разделяй, суммы не изменятся. Где интервалы? Тема не раскрыта!

(44) у них фиктивные доки... в данном случае налога большая т.к. плоха доки подделать...

(45) Я не про это. Рассматривая интервалы, в уравнении (8) должны присутствовать диапазоны, вида:
(100+40+65) - (90+26+3) = 205 - 119 = -86
( 85+25+ 2) - (90+26+3) = 112 - 119 = + 7
и мне, кагбэ, не предположить, какой связующий параметр минимизируется в этих уравнениях, может: -86 + 7 ?

+(46) из (0): "Лучшее решение является сумма промежутков на максимальную сумму подобранных чисел" - сумма промежутков - величина постоянная, максимальная сумма подобранных чисел - это сумма всех чисел. Распределить нужно все числа по всем промежуткам. Итого, минимизируем разницу между двух констант??

+(47)  из (0):
Пример:
1,2,3,4,5,6,7,8,9, 10
промежутки: 3-5, 6-8, 55 - 57
Плохое решение:
промежуток 3-5 можно подобрать значениями 3,2
А промежуток 6-8 значениями 7,1
Плохое решение: 55 - 57 подобраны все числа.
Лучшее решение: 55 - 57 подобраны (10, 9,7,6,4,3,2,1)
3-5 числа: 5
6-8 числа: 8


"Плохое решение: 55 - 57 подобраны все числа." - все числа имеют сумму 55, задача в принципе своём не может быть решена.

"Лучшее решение: 55 - 57 подобраны (10, 9,7,6,4,3,2,1)
3-5 числа: 5
6-8 числа: 8" - противоречит условию - не попали в диапазон 55-57, сумма = 42.

+(48) Опять же, про лучшее решение: разность между тремя диапазонами, даже если предположить, что задача верно решена:
55-57 (42) = -13 -15
3-5 (5) = +2 0
6-8 (8) = +2 0
Итог: -9 -15

"Неудачное" решение:
55-57 (55) = 0 -2
3-5 (0) = -3 -5
6-8 (0) = -6 -8
Итог: -9 -15

Хм... а где же..?. не знаю что))

(47) Так, но не так. Приведенные изначально примеры не совсем удачны, имхо. Как было написано выше, незаполненных рюкзаков не должно быть.

(47) Да... но при определенных ограничениях

(48) Ты плохой чтец ) Не увидел, что важно ко всем интервалам подобрать числа

что такое "сумма интервалов"?

(52) т.к. скорее всего все числа (с кол-вом отличным от 1) можно использовать несколько раз (для разных интервалов)

то задача сводится просто к максимально плотной укладке рюкзаков, т.е. пофиг нам сколько их алгоритм для одного рюкзака применяем ко всем интервалам в цикле


ЗЫ "умные" люди решают проблему не математически а организационно...делая нужные фирме 1 числа через фирму 2 (собственную по факту) которая покупает материалы и продает с нужной ценой (когда больше, когда меньше закупа, так чтобы прибыль была почти 0 справа)...

(54)+ кстати быстрейший (время предварительной подготовки и занимаемое место в БД не учитываем) алгоритм будет это сделать с имеющимся лямом чисел всевозможные суммы заранее

т.е. для всех возможно требуемых сумм от 1 до максимальная сумма заранее делаем подбор составляющих числе и в базу их

повторяем/обновляем подбор периодически при новых поступлениях чисел

в результате когда нам нужна сумма - она уже есть в базе и по индексу моментом найдется...

(54) Все числа имеют уникальный номер. Использовать одно и тоже число несколько раз нельзя.

(56) вы что по одной штуке материалы покупаете? ))

(55) Числа уникальны и их общая сумма обычно значительно больше чем сумма интервалов. И задача стоит оптимально утрамбовать рюкзаки.

Не понимаю в чем выгода хранить общую сумму всех чисел.
Дробить числа нельзя.

(57) Это уже коммерческая тайна ).... но вот есть такая особенность)

ответь на (53)

(58) выгода в том чтобы расчет заранее сделать когда числа приходят на склад...а когда нужна сумма при производстве уже готовые наборы чисел просто искать по требуемой сумме

(60) Сумма максимальных значений интервалов

(61) Сумма всех чисел ? ну допустим имеем числа на сумму 100, а интервалов на 50... что это дает?

задача называется "Мультипликативный рюкзак"

(64) Почему "мультипликативный"? Вроде никаких умножений нет.

(63) причем тут это?

допустим максимальная сумма (которую возможно нужно подобрать) 10 миллионов

тогда заранее считаем-рассчитываем все 10 миллионов комбинаций (реально меньше выйдет т.к. не все получится подобрать)

сумма 1: числа 1
сумма 2: числа 2
сумма 3: числа 1+2, 3
сумма 4: числа 1+3, 4
сумма 5: числа 1+4, 2+3, 5
сумма 6: числа 1+5, 1+2+3, 2+4, 6

и т.д.

т.е. числа то известны ведь заранее (раньше чем требуемая к подбору сумма) и их количество ограничено (1 миллион)

значит все комбинации чисел (с получаемой ограниченной сверху суммой) можно заранее найти

записать их в базу данных и юзать быстро находя когда нужно

(66) Найти надо сразу все комбинации без пересечений.
И числа становятся известны только в момент расчета (

(67) "числа становятся известны только в момент расчета" - это вы искусственно себя ограничили

что все числа не спорю, но они же приходят/уходят постепенно? не бывает так что все документы производства делаются разом 31 декабря за весь год с 1 января...

(68) Естественно, но большинство вконце месяца. И все же не вижу выгоды сформировали N набор и этих наборов может быть больше чем самих чисел.

Изучай
http://www.informatik.uni-kiel.de/fileadmin/arbeitsgruppen/theory_of_paralle/Publications/Pub2009/fast-long.pdf
A fast approximation scheme for the multiple knapsack problem

(70) Не уверен, что пригодна для нужной ТС размерности: требуется релаксация к задаче линейного программирования (правда специального вида).

(69) вместо операций подбора, сложения и сравнения

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

т.е. 5 сек и нужные числа для нужных сумм подобраны (найдены в базе), понятно что базу надо обновлять

(72)+ кстати тут "зачем" это вопрос из разряда "а зачем в 1С нужны регистры накопления" ?

можно же когда надо просто документы сложить...вычесть...

(70) Толковая книженция

Кстати чтобы понятнее ))

Вместо того чтобы рассчитывать себестоимость производства продукции в момент проведения дока производства (по спецификации)

Можно заранее рассчитать всевозможные себестоимости для всех спецификаций (из N сырья получают продукцию) в момент заведения спецификации

Зная на момент заведения цены всех поступлений сырья

Понятно про при новом поступлении сырья (новая цена) надо возможные себестоимости для спецификаций пересчитать...

(60) Для одного значения суммы может быть много комбинаций получения суммы. Например, если все числа = 1 и их всего 2n, то для сумма = n число комбинаций будет = число сочетаний из 2n по n.
Для многократного решения задачи о ранце (с разными значениями его емкости ) это имеет смысл. Для задачи ТС реализация идеи мне неясна.

Тут, по задаче, даже метод динамического программирования использовать не рекомендуется, он потребует 4 террабайта памяти в особо оптимизированном случае. А если ещё и возвести в количество вариантов (в степень 100 000) - понятно, что даже дюже оптимизированный способ разворачивания подготовительных данных не влезет в базу данных, не то что все сочетания ко всем количествам.

В задаче главное скорость или величина разницы?

(78) оба важны.
Реализация через динамическое программирование показала хорошую работу (подобрало все точь в точь), но крайне медленную скорость, на тестовых данных.

Если жадный алгоритм справлялся за секунды на 1000 предметах и 100 рюкзаках, то динамическое выполняется часами.

(79) Что не приемлимо.

(80)  + В динамическом особая проблема заключается в формировании двухмерного массива, если размер рюкзака 100000 и больше, то матрица из 100 предметов получается 100000*100...

Вопрос математикам, Может есть возможность сбора массива с конца, что бы остановиться посередине пути и выбрать подходящую комбинацию.

?

ну скорость даже близко приближающуюся к жадному алгоритму ты не получишь никак. можешь попробовать метод ветвей и границ, но он все равно близок к методу полного перебора и скорее всего медленнее динамического программирования.

Нужно юзать параллельные вычисления и явно не на 1с

Каков алгоритм реализации через динамическое программирование?

(84) И пробовать не стоит: пустая трата времени.
Если немного "наплевать" на отрицательную маржу по некоторым товарам (с сохранением общей положительной), я бы добавил чего-нибудь в ранцы, в которых большая разница между выручкой и себестоимостью.
Типа:
- отсортировать "ранца" по разнице между выручкой и себестоимостью по убыванию;
- отсортировать оставшиеся "материалы" по возрастанию;
- добавлять в "ранцы" "материалы" с контролем % превышения себестоимости над выручкой.

(86)
for i = 0..W
  A[0][i] = 0;
for i = 0..N
  A[i][0] = 0;   //Первые элементы приравниваем к 0
for k = 1..N              
  for s = 0..W   //Перебираем для каждого k все вместимости
    if s >= w[k]    //Если текущий предмет вмещается в рюкзак
      A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); //выбираем класть его или нет
    else
      A[k][s] = A[k-1][s];             //иначе, не кладем
Затем найдем набор ans предметов, входящих в рюкзак, рекурсивной функцией:
findAns(k, s)
  if A[k][s] == 0
    return;
  if A[k-1][s] == A[k][s]
    findAns(k-1, s);
  else
    findAns(k-1, s - w[k]);
    ans.push(k);

http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_рюкзаке

(85) Ну хочется не секунды, но пусть минуты... но не когда 1000 предметов на 100 ранцев рассчитывается почти сутки.

(85) Какие идеи распараллеливания? Просто если параллельно два разных ранца используют один и тот же предмет, то возникнет конфликт, как его решать?

Есть ещё вариант - симплекс-метод. Максимизация результата по 100 000 переменным и 200 000 неравенствам. Обычный алгоритм говорит, что взять 0.236 раза первую цену, 0.17 пятую и 0.63 раза восьмую, остальные не брать... Так вот задача только в том, чтобы реализацию на целых числах найти.

судя по всему, задача NP-полная, потому точного решения не получится найти.
Я бы подумал в сторону динамических алгоритмов: ищем какое-то решение, после чего пытаемся несколькими перестановками получить более оптимальное решение

(92) Динамический алгоритм уже есть, скорость не устраивает )))  смотри (88)

(93) он не линамический, вы там перебираете все счетания интервалов-числел

(94) Есть ли описание и пример?

(92) Ну это вы про метод ветвей и границ и говорите )

(95) динамический - это как-то так:
1. перебираем все интервалы и для каждого берем первое попавшееся число. сложность порядка 100 тыс.
2. после этого берем случайный интервал и подбираем для него оптимальное число. Сложность порядка 1 млн.

п.2 применяем до тех пор, пока не надоест. при этом цедевая функция будет постепенно минимизироваться.

(96) NP-полнота - это характеристика задачи а не алгоритма

(98) я про вторую часть высказывания про алгоритмы.

(92) "ищем какое-то решение, после чего пытаемся несколькими перестановками" (97) "после этого берем случайный интервал" - вы не на метод Монте-Карло, случаем, намекаете?

Будет как в анекдоте:
- Доктор, у меня что-то болит
- Пожалуйста, вот вам какая-то таблетка...

(91) Хотел бы я посмотреть на задачу ЛП с такой матрицей.
Тем более я Вам сразу скажу ответ: все неравенства на вес ранцев сядут на равенства и сумма "материалов" = сумме "ранцев".
(92) Классификация сложности задачи о ранце довольно хорошо известна (лень давать ссылку).

(102) Равно - не равно - на целых числах СМ зацикливается. Пока не победил. В интернетах описания для дискретных данных не нашёл, но из чертогов разума доносится, что мет0ды есть, а вот какие - не помню...

Пока решил так:
- Жадным алгоритмом выбираем вариант заполнения рюкзака.
- случайным образом подбираю еще 100 наборов для рюкзака и выбираю лучший.

Скорость приемлемая, но и результат не всегда ...

(104) хорошо подойдет генетический алгоритм. Я так задачу коммивояжера решал когда-то. Плюс ген алгоритма, что можно легко добавлять новые условия

и не нужно выдумывать свое в задачах в которых правильные подходы давно найдены

(105) А есть ли пример, так как по вики я сужу что мой алгоритм уже обладает зачатками генетического...

(107) на 1с примера нету, мне очень была важна скорость и я писал com объект. Если коротко, то случайным образом создаете своих 100 вариантов (начальная популяция). Из них выбираете 50 лучших(приспособленность). Потом немного их модифицируя (скрещивая попарно) получаете снова 100. Мутацию на первых парах можете опустить, что бы не забивать голову потом когда основной код будет работать добавите (мутация не сильно влияет на результат)

(107) вот тут http://art4art.narod.ru/ga_intro.html на джаве есть решение

(107) Не придавайте серьезного значения утверждениям в (105) и в (106).
Коммивояжер изъезжен вдоль и поперек и вовсе не общими схемами. Генетические алгоритмы - это не алгоритмы, а некая общая схема. По-моему, ничуть не лучше случайного выбора и примерно такой же оптимальности.
(105) Попробуйте генетическим "алгоритмом" задачу Штейнера решить для скажем, 30 точек.

(100) очень смешно. Вы решали задачу коммивояжера в реальной жизни? )

(100) -> (110)

(108) Как происходит скрещивание? Заменой предметами в случайном порядке? Потом опять отбор и выбор лучшего?.

Мутация как я понимаю это подмена из свободного пула предмета ?

(110) Тоже не вижу выигрыша по сравнению с случайным выбором предметов, а наоборот потеря времени на скрещивание...

(114) все суть в том что вы делаете не случайный выбор, а производите некое уточнение результата

(112) Да: какое-то представление о дискретных задач у меня есть. Правда, давно отошел от дел.
Предлагаю Вам написать генетический алгоритм для решения системы неравенств в булевых переменных:
3*X1+3*X2+...+3*X1000<=1499
3*X1+3*X2+...+3*X1000>=1498
Xi = 0 или 1.
Если алгоритм через обозримое время выдаст решение или ответ, что решения нет, я перечисляю Вам 10 000 руб.

(116) забыли уточнить на чем алгоритм будет выполняться

параллельный генетический на кластере из 1000 компов или обычный не параллельный на одном компе?

(117) На чем хотите: число компов сокращает время в лучшем случае линейно.