powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Распределить массив на группы по весам
17 сообщений из 17, страница 1 из 1
Распределить массив на группы по весам
    #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
Распределить массив на группы по весам
    #40117357
godsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
если равномерно, то есть
NTILE (integer_expression) OVER ( [ <partition_by_clause> ] < order_by_clause > )
Распределяет строки упорядоченной секции в заданное количество групп. Группы нумеруются, начиная с единицы. Для каждой строки функция NTILE возвращает номер группы, которой принадлежит строка.


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

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


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


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

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

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

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

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

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

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

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

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

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

У Вас комплексы какие-то?
Не имеете желания помочь, проходите мимо. Не надо флудить.
...
Рейтинг: 0 / 0
Распределить массив на группы по весам
    #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
Распределить массив на группы по весам
    #40117678
Владислав Колосов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Двоичник,

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


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