|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
Условие: Есть некое количество бананов, расфасованных по нескольким упаковкам. В каждой упаковке разное количество бананов. Задача: Равномерно разложить бананы в упаковках по корзинам. Делить упаковку нельзя. Пример: упаковка 1 - 10 бананов; упаковка 2 - 3 банана; упаковка 3 - 2 банана; упаковка 4 - 1 банан. 2 корзины. Должно получиться - корзина1 (упаковка 1), корзина2 (упаковка 2, упаковка 3, упаковка 4). Хочется найти решение на SQL. Напрашивается ntile() по бананам, но не понимаю как привязать условие с неделением упаковки. Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40.
IDPACKBANANABUCKET1pack_1banana_112pack_1banana_1013pack_1banana_214pack_1banana_315pack_1banana_416pack_1banana_517pack_1banana_618pack_1banana_719pack_1banana_8210pack_1banana_9211pack_2banana_11212pack_2banana_12213pack_3banana_13214pack_3banana_14215pack_3banana_15216pack_4banana_162 Как видно из примера, banana_8, banana_9 из упаковки pack_1 присвоены 2-ой корзине, что противоречит условию. Прошу совета. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 16:23 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
watson, похоже на задачку про рюбзачек https://www.sql.ru/forum/actualsearch.aspx?search=knapsack&sin=0&bid=3&a=&ma=0&dt=-1&s=1&so=1 http://vbegun.blogspot.com/2005/11/sql-puzzle-iii.html ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 16:35 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
watsonРавномерно Критерии равномерности? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 16:37 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
-2-Критерии равномерности? чтобы количество бананов в каждой корзине было максимально равным, учитывая что упаковку делить нельзя. Staxwatson, похоже на задачку про рюбзачек https://www.sql.ru/forum/actualsearch.aspx?search=knapsack&sin=0&bid=3&a=&ma=0&dt=-1&s=1&so=1 http://vbegun.blogspot.com/2005/11/sql-puzzle-iii.html ..... stax буду читать, благодарю. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 17:01 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
watson, чтобы суммы всех QTY каждой группы были максимально близки друг другу Кто встречался с подобной проблемой і тд .... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 17:06 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 17:11 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
watson-2-Критерии равномерности? максимально равнымравным чему? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 17:17 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
-2-watsonпропущено... максимально равнымравным чему? "среднему значению" sum(банан)/к-во корзин ps "дисперсия" минимальна .... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 17:28 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
Stax"среднему значению" sum(банан)/к-во корзин Ну тогда greatest(max(размер-упаковки),ceil(sum(банан)/к-во корзин)) SY. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 18:09 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
От блин а я тут на днях голову ломала как файлы данных распределить равномерно по потокам с учетом их объема. И ничего умнее не придумала, как отсортировать и брать по одну в группу с учетом максимума размера предыдущих групп :)) А нада было погуглить по слову рюкзачек )) ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 19:34 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
SYStax"среднему значению" sum(банан)/к-во корзин Ну тогда greatest(max(размер-упаковки),ceil(sum(банан)/к-во корзин)) SY.Не очень понятно как, например, при упаковках с количеством (1,2,3,10,100) и трех корзинах такой подход распределит (1,2,3), (10), (100). Впрочем, еще менее понятно при чём здесь рюкзак. Я веду речь, когда критерий оптимальности - минимум дисперсии по корзинам. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 19:45 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
КобанчегВпрочем, еще менее понятно при чём здесь рюкзак. Корзина = рюкзак. T.е. есть рюкзаки вместимoстью N упаковок и 5 упаковок с разным количеством товара которые нужно разложить по рюкзакам. Как именно разложить требует уточнения задачи - набить максимально, т.е. (100), (1,2,3,10), пустой (минимизация числа корзин), минимум дисперсии по корзинам (с/без ограничения числа корзин) или ещё чего... SY. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 20:16 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
SYКобанчегВпрочем, еще менее понятно при чём здесь рюкзак. Корзина = рюкзак. T.е. есть рюкзаки вместимoстью N упаковок и 5 упаковок с разным количеством товара которые нужно разложить по рюкзакам. Как именно разложить требует уточнения задачи - набить максимально, т.е. (100), (1,2,3,10), пустой (минимизация числа корзин), минимум дисперсии по корзинам (с/без ограничения числа корзин) или ещё чего... SY. задача забить все корзины/рюкзаки. в прикладном смысле - хочу разбить обработку данных на потоки. корзина - один поток. то есть изначальное множество данных надо разделить по потокам, учитывая то, что в "упаковке" данные между собой зависимы и, следовательно, должны обрабатываться одним потоком. количество данных (строк) в каждом потоке должно быть максимально близко к количеству данных (строк) в другом, учитывая ограничение зависимости данных в упаковке. похоже, что решение на SQL нетривиальное, поэтому буду писать на pl/sql. в любом случае, если кто-то напишет на sql, будет любопытно взглянуть. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 23:11 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
SYКорзина = рюкзак. T.е. есть рюкзаки вместимoстью N упаковок и 5 упаковок с разным количеством товара которые нужно разложить по рюкзакам.Алгоритмы для задачи о рюкзаке рассчитаны на один рюкзак а не несколько. И они максимизируют ценность с жестким лимитом на вместимость. В случае ТС ничего страшного не будет, если какая-то корзина чуть превысит лимит (если мы минимизируем дисперсию). SYКак именно разложить требует уточнения задачи - набить максимально, т.е. (100), (1,2,3,10), пустой (минимизация числа корзин)Если минимизируем число корзин (странный критерий если цель распределить по n корзинам), то почему бы не засунуть всё в одну. watsonв любом случае, если кто-то напишет на sql, будет любопытно взглянуть. :)А как ты будешь проверять если не в состоянии озвучить критерий оптимальности? Минимизация дисперсии корзин требует слишком большой вычислительной сложности. Полный перебор - корзины в степени упаковки. Его наверняка можно как-то сократить, но все равно будет очень долго. Соответственно можно смотреть на приближенные распределения, например 1) либо совсем забить на число бананов и распределять по mod(ora_hash(упаковка), число корзин) 2) либо кумулятивную сумму распределять по бакетам (более-менее нормально работает если нет упаковок больших чем размер корзины. если такие есть - их предварительно можно определить в отдельные корзины) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32.
Все будет уже не так симпатично если 20 заменить на 30 или вообще 100. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 02:19 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
watsonто есть изначальное множество данных надо разделить по потокамЗадача параллельной обработки решается проще - очередь. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 06:41 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
Кобанчег(более-менее нормально работает если нет упаковок больших чем размер корзины . если такие есть - их предварительно можно определить в отдельные корзины)Корзина имеет неограниченный объем. Если есть упаковки более среднего, то каждая из них "предварительно" идет в отдельную корзину, но это не исключает корзины из дальнейшего распределения. Алгоритм последовательного раскладывания упаковок можно улучшить, если упаковки сортировать по убыванию и на каждой итерации выбирать пустейшую корзину. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 07:08 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
SYКобанчегВпрочем, еще менее понятно при чём здесь рюкзак. Корзина = рюкзак. T.е. есть рюкзаки вместимoстью N упаковок и 5 упаковок с разным количеством товара которые нужно разложить по рюкзакам. Как именно разложить требует уточнения задачи - набить максимально, т.е. (100), (1,2,3,10), пустой (минимизация числа корзин), минимум дисперсии по корзинам (с/без ограничения числа корзин) или ещё чего... SY. імхо Корзина = рюкзак. T.е. есть рюкзаки вместимoстью N бананов ... ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 08:39 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
DВАИ ничего умнее не придумала, как отсортировать и брать по одну в группу с учетом максимума размера предыдущих групп :))Следующего в сторону уменьшения класть в наипустейшую "корзину"? - Простой и понятный алгоритм без изысков. "Палатки" здесь не нужны. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 09:00 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
-2-упаковки сортировать по убыванию и на каждой итерации выбирать пустейшую корзину.Пример неоптимального результата деления 7,8,3,2,2 по двум корзинам: Код: plsql 1. 2. 3. 4.
... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 09:16 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
-2-Пример неоптимального результата деления 7,8,3,2,2 по двум корзинамВ общем-то, достаточно хорошее компромиссное решение с отклонением от оптимального всего в ±1, зато затраты всего лишь на сортировку. В принципе, его можно немного улучшить (в случае диспетчера очередей, т.е. когда диспетчер знает у какой очереди сколько еще осталось обработать) - при снижении кол-ва необработанных до допустимого, переходить на полный перебор. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 12:29 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
-2-Кобанчег(более-менее нормально работает если нет упаковок больших чем размер корзины . если такие есть - их предварительно можно определить в отдельные корзины)Корзина имеет неограниченный объем. Если есть упаковки более среднего, то каждая из них "предварительно" идет в отдельную корзину, но это не исключает корзины из дальнейшего распределения.Под размером понимался ожидаемый размер = число бананов/число корзин. В примере выше, если имеем 100 для одной из упаковок, убираем ее (в третью корзину) и уменьшаем число корзин на 1. Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31.
-2-Алгоритм последовательного раскладывания упаковок можно улучшить, если упаковки сортировать по убыванию и на каждой итерации выбирать пустейшую корзину.Выглядит более изящно, но интересно реализуемо ли SQL-но без model/rec with. Напоминает заправки . ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 13:19 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
StaxКорзина = рюкзак. T.е. есть рюкзаки вместимoстью N бананов ... Максимально набить один рюкзак или равномерно набить n рюкзаков это вообще перпендикулярные вещи. Единственно, что общее это экспоненциальная сложность полного перебора, так что да, в этом схожесть на подход Бегуна. Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23.
... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 14:08 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
Кобанчег, На всякий случай замечу, что если решать задачу в формулировке ТС - "минимизировать дисперсию", то количество корзин всегда равно 1. Просто пихай все в одну корзину, дисперсия 0, все абсолютно равномерно разделилось. Меньше нуля дисперсию получить нельзя. Есть ощущение что ТС и сам не очень хорошо представляет чего он хочет. Но если он хочет разделить данные на потоки, то предположу что он хотя бы знает сколько потоков он хочет. Предположим он хочет N потоков. Тогда нам нужен бинарный поиск по variance - разнице между максимальной и минимальной корзиной. При фиксированном variance мы легко определим сколько должно быть в максимальной корзине - пусть это K. Выделить из ящиков поднабор ящиков общей суммой K можно без полного перебора с помощью динамического программирования ( гуглить по "задача о рюкзаке динамическое программирование" ). От стандартной задачи это отличается тем что нам нужно найти не одно решение, а все ( т.к. для каких-то из этих решений может не оказаться решений на следующей итерации, поэтому мы вынуждены проверить все). После чего решаем ту же задачу для оставшихся ящиков и корзины на одну меньше и с уже известным variance. Это решение работает гораздо быстрей чем полный перебор. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 15:13 |
|
Разделить количество бананов в упаковке по корзинам - buckets (SQL?)
|
|||
---|---|---|---|
#18+
ElicDВАИ ничего умнее не придумала, как отсортировать и брать по одну в группу с учетом максимума размера предыдущих групп :))Следующего в сторону уменьшения класть в наипустейшую "корзину"? - Простой и понятный алгоритм без изысков. "Палатки" здесь не нужны. да, но не гарантирующий (?) максимально равномерного распределения ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 15:43 |
|
|
start [/forum/topic.php?fid=52&msg=39829023&tid=1882366]: |
0ms |
get settings: |
11ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
43ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
56ms |
get tp. blocked users: |
1ms |
others: | 252ms |
total: | 397ms |
0 / 0 |