|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
Всезнающий all Помогите пожалуйста, написать скрипт, который выполнит задачу в соответствии с постановкой и ожиданиям. Есть массив однородных данных, с различными и повторяющимися значениями - весами. Массив имеет динамическое количество элементов. value 1 2 4 6 8 9 17 25 6 2 4 11 24 6 15 89 56 2 6 И имеется входной параметр: 4 Необходимо разделить равномерно от суммарного веса элементов массива раскидать на 4 группы один из вариантов, выбрать максимально тяжелый элемент, и в другие группы набирать массу не превышающую массу самого тяжелого: value group 89 1 56 2 25 2 8 2 24 3 17 3 15 3 11 3 9 3 6 3 6 3 1 3 2 4 4 4 6 4 6 4 2 4 4 4 2 4 Либо как вариант, в первой группе оставить самый тяжелый, а в оставшиеся группы равномерно распределить оставшиеся: value group 89 1 56 2 11 2 1 2 25 3 8 3 24 3 9 3 2 3 17 4 15 4 6 4 6 4 4 4 6 4 6 4 2 4 4 4 2 4 Никак не могу совладать. Помогите пожалуйста Спасибо огромное Извините за оформление в текстовом формате. Я думаю тут все понятно. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 14:12 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
если равномерно, то есть NTILE (integer_expression) OVER ( [ <partition_by_clause> ] < order_by_clause > ) Распределяет строки упорядоченной секции в заданное количество групп. Группы нумеруются, начиная с единицы. Для каждой строки функция NTILE возвращает номер группы, которой принадлежит строка. PS. про "динамический массив" - не понял ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 14:59 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
godsql, ntile не пойдет, пробовал Он всем элементам, каждому даст группу. получится, что в одной группе будет самый тяжелый, и элементы полегче. Но он сделает разделение одинаковое по количеству элементов в каждую группу. Это не то что мне надо. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 15:20 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
godsql PS. про "динамический массив" - не понял Количество элементов в массиве может быть различным. И не фиксировано ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 15:21 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
вообще-то, такие задачи в sql особо не решаются. поскольку тут тупо перебор всех возможных комбинаций сумм ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 19:12 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
https://ru.wikipedia.org/wiki/Задача_разбиения_множества_чисел Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования и существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной задачей"[1]. Существует оптимизационная версия задачи разбиения, в которой требуется разбить мультимножество S на два подмножества S1 и S2, таких, что разность между суммой элементов S1 и суммой элементов S2 минимальна. Оптимизационная версия является NP-трудной задачей, но на практике может быть решена эффективно[2]. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 19:47 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
godsql вообще-то, такие задачи в sql особо не решаются. поскольку тут тупо перебор всех возможных комбинаций сумм Потому что это NP-полная задача укладки рюкзака. https://ru.wikipedia.org/wiki/Задача_о_рюкзаке ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 19:47 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
Если чисел "дохера" - простейший алгоритм заключается в следующем: 1. Случайным образом сортируем все числа. 2. Берем по 1/4 этой последовательности. ЗЫ. При стремлении множества к бесконечности, результат будет стремиться к "истинному делению множества на 4-е равные части". ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 19:51 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
aleks222 Если чисел "дохера" - простейший алгоритм заключается в следующем: 1. Случайным образом сортируем все числа. 2. Берем по 1/4 этой последовательности. ЗЫ. При стремлении множества к бесконечности, результат будет стремиться к "истинному делению множества на 4-е равные части". ну да, я хотел предложить вычислить веса, а потом складывать "последний" с "первым" по достижении суммы 1/4. Оно где-то так группы и будут ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 20:26 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
uaggster godsql вообще-то, такие задачи в sql особо не решаются. поскольку тут тупо перебор всех возможных комбинаций сумм Потому что это NP-полная задача укладки рюкзака. https://ru.wikipedia.org/wiki/Задача_о_рюкзаке я понимаю, но вот на скуле это решать как-то не думал :) ... |
|||
:
Нравится:
Не нравится:
|
|||
04.12.2021, 20:29 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
Я то могу это сделать на языке скуля, организовать циклы, переборы, наполнение. Но это не изящно. Хотелось бы селектом, без циклов. Может рекурсивно cte использовать, но пока не хватает фантазии это воплотить Потому и обратился за помощью к вам ... |
|||
:
Нравится:
Не нравится:
|
|||
05.12.2021, 13:14 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
Двоичник Я то могу это сделать на языке скуля, организовать циклы, переборы, наполнение. Но это не изящно. Хотелось бы селектом, без циклов. Может рекурсивно cte использовать, но пока не хватает фантазии это воплотить Потому и обратился за помощью к вам Надо быть честным с собой - никак ты не могешЪ. И надеешься на доброго дядю. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.12.2021, 14:34 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
aleks222, У Вас комплексы какие-то? Не имеете желания помочь, проходите мимо. Не надо флудить. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.12.2021, 15:12 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
Двоичник Никак не могу совладать. Помогите пожалуйста делал такое недавно - для регулярной проверки делил базы на 4 части исходя из общего размера код Код: sql 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
05.12.2021, 18:43 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
Двоичник, отсортируйте элементы по весу, разделите на 4 равные части по количеству, затем возьмите по четверти от каждой четверти и получите новые группы. Приближение линейное, но какую-то точность получите. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.12.2021, 11:00 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
Код: sql 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. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55.
как-то немного странно получилось.... Я отвязал от своего окружения скрипт и в качестве данных взял выборку Код: sql 1.
На выходе я получил: (смотрим в картинку в аттаче) в первом рюкзаке 39 предметов, суммарным весом 90 единиц. а в девятом 36 предметов, суммарным весом 180 единиц. Что-то перевес... ... |
|||
:
Нравится:
Не нравится:
|
|||
06.12.2021, 13:27 |
|
Распределить массив на группы по весам
|
|||
---|---|---|---|
#18+
Двоичник, а так подходит? Код: sql 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
06.12.2021, 15:06 |
|
|
start [/forum/topic.php?fid=46&msg=40117350&tid=1684043]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
137ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
55ms |
get tp. blocked users: |
1ms |
others: | 14ms |
total: | 252ms |
0 / 0 |