Гость
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Распределить массив на группы по весам / 17 сообщений из 17, страница 1 из 1
04.12.2021, 14:12
    #40117350
Двоичник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
Всезнающий 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


Никак не могу совладать. Помогите пожалуйста
Спасибо огромное

Извините за оформление в текстовом формате. Я думаю тут все понятно.
...
Рейтинг: 0 / 0
04.12.2021, 14:59
    #40117357
godsql
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
если равномерно, то есть
NTILE (integer_expression) OVER ( [ <partition_by_clause> ] < order_by_clause > )
Распределяет строки упорядоченной секции в заданное количество групп. Группы нумеруются, начиная с единицы. Для каждой строки функция NTILE возвращает номер группы, которой принадлежит строка.


PS. про "динамический массив" - не понял
...
Рейтинг: 0 / 0
04.12.2021, 15:20
    #40117358
Двоичник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
godsql,

ntile не пойдет, пробовал
Он всем элементам, каждому даст группу. получится, что в одной группе будет самый тяжелый, и элементы полегче. Но он сделает разделение одинаковое по количеству элементов в каждую группу. Это не то что мне надо.
...
Рейтинг: 0 / 0
04.12.2021, 15:21
    #40117359
Двоичник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
godsql


PS. про "динамический массив" - не понял


Количество элементов в массиве может быть различным. И не фиксировано
...
Рейтинг: 0 / 0
04.12.2021, 19:12
    #40117374
godsql
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
вообще-то, такие задачи в sql особо не решаются.
поскольку тут тупо перебор всех возможных комбинаций сумм
...
Рейтинг: 0 / 0
04.12.2021, 19:47
    #40117378
aleks222
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
https://ru.wikipedia.org/wiki/Задача_разбиения_множества_чисел

Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования и существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной задачей"[1].

Существует оптимизационная версия задачи разбиения, в которой требуется разбить мультимножество S на два подмножества S1 и S2, таких, что разность между суммой элементов S1 и суммой элементов S2 минимальна. Оптимизационная версия является NP-трудной задачей, но на практике может быть решена эффективно[2].
...
Рейтинг: 0 / 0
04.12.2021, 19:47
    #40117379
uaggster
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
godsql
вообще-то, такие задачи в sql особо не решаются.
поскольку тут тупо перебор всех возможных комбинаций сумм

Потому что это NP-полная задача укладки рюкзака.
https://ru.wikipedia.org/wiki/Задача_о_рюкзаке
...
Рейтинг: 0 / 0
04.12.2021, 19:51
    #40117380
aleks222
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
Если чисел "дохера" - простейший алгоритм заключается в следующем:
1. Случайным образом сортируем все числа.
2. Берем по 1/4 этой последовательности.

ЗЫ. При стремлении множества к бесконечности, результат будет стремиться к "истинному делению множества на 4-е равные части".
...
Рейтинг: 0 / 0
04.12.2021, 20:26
    #40117384
godsql
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
aleks222
Если чисел "дохера" - простейший алгоритм заключается в следующем:
1. Случайным образом сортируем все числа.
2. Берем по 1/4 этой последовательности.

ЗЫ. При стремлении множества к бесконечности, результат будет стремиться к "истинному делению множества на 4-е равные части".

ну да, я хотел предложить вычислить веса, а потом складывать "последний" с "первым" по достижении суммы 1/4.
Оно где-то так группы и будут
...
Рейтинг: 0 / 0
04.12.2021, 20:29
    #40117385
godsql
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
uaggster
godsql
вообще-то, такие задачи в sql особо не решаются.
поскольку тут тупо перебор всех возможных комбинаций сумм

Потому что это NP-полная задача укладки рюкзака.
https://ru.wikipedia.org/wiki/Задача_о_рюкзаке

я понимаю, но вот на скуле это решать как-то не думал :)
...
Рейтинг: 0 / 0
05.12.2021, 13:14
    #40117444
Двоичник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
Я то могу это сделать на языке скуля, организовать циклы, переборы, наполнение.
Но это не изящно. Хотелось бы селектом, без циклов. Может рекурсивно cte использовать, но пока не хватает фантазии это воплотить
Потому и обратился за помощью к вам
...
Рейтинг: 0 / 0
05.12.2021, 14:34
    #40117456
aleks222
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
Двоичник
Я то могу это сделать на языке скуля, организовать циклы, переборы, наполнение.
Но это не изящно. Хотелось бы селектом, без циклов. Может рекурсивно cte использовать, но пока не хватает фантазии это воплотить
Потому и обратился за помощью к вам

Надо быть честным с собой - никак ты не могешЪ.
И надеешься на доброго дядю.
...
Рейтинг: 0 / 0
05.12.2021, 15:12
    #40117461
Двоичник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
aleks222,

У Вас комплексы какие-то?
Не имеете желания помочь, проходите мимо. Не надо флудить.
...
Рейтинг: 0 / 0
05.12.2021, 18:43
    #40117500
komrad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
Двоичник


Никак не могу совладать. Помогите пожалуйста


делал такое недавно - для регулярной проверки делил базы на 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.
	/*get section size in GBs*/
	select @section=1.01*convert(numeric(10,1),sum(iif(type_desc='ROWS',size/128./1024,0)))/4 
	from sys.master_files 
	where database_id>4
	and state_desc='ONLINE'

	;with sections
	as
	(
		select 0*@section    [min],     1*@section [max],      1     [i] 	union all
		select 1*@section+1  [min], 	2*@section [max],      2     [i]	union all
		select 2*@section+1  [min], 	3*@section [max],      3     [i]	union all
		select 3*@section+1  [min], 	4*@section [max],      4     [i]	union all
		select 4*@section+1  [min], 	5*@section [max],      5     [i]
	)
	,     data
	as
	(
		select database_id                                
		,		db_name(database_id)                        [name]
		,		convert(numeric(10,1),sum(iif(type_desc='ROWS',size/128./1024,0))) [sizeGB]
		,		SUM(convert(numeric(10,1),sum(iif(type_desc='ROWS',size/128./1024,0)))) OVER (ORDER BY newid()) [sum]
		from sys.master_files
		where database_id>4
		and state_desc='ONLINE'
		group by database_id
	)
	
	insert into dbo.dbcc_databases ( dt, name, sizeGB, n, done )
	select 
		getdate()
		,d.name
		,d.sizeGB
		,s.i [n]
		,0
	from data     d
	join sections s on d.sum between s.min and s.max

...
Рейтинг: 0 / 0
06.12.2021, 11:00
    #40117678
Владислав Колосов
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
Двоичник,

отсортируйте элементы по весу, разделите на 4 равные части по количеству, затем возьмите по четверти от каждой четверти и получите новые группы. Приближение линейное, но какую-то точность получите.
...
Рейтинг: 0 / 0
06.12.2021, 13:27
    #40117746
Двоичник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам

Код: 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.
if object_id('tempdb..#bag') is not null drop table #bag 
if object_id('tempdb..#rucksack') is not null drop table #rucksack
if object_id('tempdb..#sections') is not null drop table #sections

create table #bag (id bigint , deep bigint)
declare @section numeric(22,8)

set nocount on

;with cte (id, deep) as (
select map_id, dest_datatype_id from msdb..MSdbms_datatype_mapping
)

insert into #bag select * from cte order by deep desc

declare @i int = 1, @j int = 10 --количество рюкзаков

select @section = sum(deep)/@j from #bag

create table #sections (id_rucksack bigint identity, vmin bigint, vmax bigint)

while @i <= @j
	begin

		insert into #sections
		select @section * (@i-1), @section * @i

		set @i = @i + 1
	end

	;with 
	data as (
		select
		 id,
		 sum(deep) as sum_deep,
		 SUM(sum(deep)) OVER (ORDER BY id) [sum]
		from #bag
		group by id
	)

	select 	
		d.id,
		d.sum_deep,
		s.id_rucksack
	into #rucksack		
	from data d
	join #sections s on d.sum between s.vmin and s.vmax

	select id_rucksack, 
		max(sum_deep) as max_sum_deep_per_rucksack, 
		count(1) as count_per_rucksack
	from #rucksack
	group by id_rucksack

	select id_rucksack, id from #rucksack order by 1, 2




как-то немного странно получилось....

Я отвязал от своего окружения скрипт и в качестве данных взял выборку
Код: sql
1.
select map_id, dest_datatype_id from msdb..MSdbms_datatype_mapping



На выходе я получил: (смотрим в картинку в аттаче)
в первом рюкзаке 39 предметов, суммарным весом 90 единиц.
а в девятом 36 предметов, суммарным весом 180 единиц.

Что-то перевес...
...
Рейтинг: 0 / 0
06.12.2021, 15:06
    #40117800
komrad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Распределить массив на группы по весам
Двоичник,

а так подходит?
Код: 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.
drop table if exists #rucksack5 

declare @seg numeric(10,1) /*rugsak size*/
declare @i smallint /*amount of rugsaks*/ = 10

select @seg=1.01*sum(dest_datatype_id) / @i
from msdb..MSdbms_datatype_mapping

;with segs (id, st,en) as 
(
	select top (@i) map_id [n], (map_id-1)*@seg, map_id*@seg 
	from msdb..MSdbms_datatype_mapping
	where map_id<=@i+1
)
,data as (
		select
			 map_id,
			dest_datatype_id [item_w],
			SUM(dest_datatype_id) OVER (ORDER BY map_id) [sum]
		from msdb..MSdbms_datatype_mapping
		)
select 	
		d.map_id,
		item_w,
		s.id [rug_id],
		d.[sum]
	into #rucksack5
	from data d
	join segs s on (d.sum>=s.st and d.sum<s.en)

select @seg [rugzak_size]

select 
	rug_id
	,count(1) [items]
	,sum(item_w) [items_weight]
	, sum([sum]) [ttl_size]
from #rucksack5
group by rug_id

...
Рейтинг: 0 / 0
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Распределить массив на группы по весам / 17 сообщений из 17, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]