Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
Добрый день.
Прошу помочь с задачей, которая сводится к решению следующего:
Есть таблица с ключем ID и кол-вом показателей Num
if object_id('tempdb..#Numbers') is not null
	drop table #Numbers
create table #Numbers
(
	ID  int,
	Num int
)

insert into #Numbers
		  select  1 as ID,  3 as Num
union all select  2 as ID,  5 as Num
union all select  3 as ID,  2 as Num
union all select  4 as ID,  7 as Num
union all select  5 as ID,  1 as Num
union all select  6 as ID,  8 as Num
union all select  7 as ID, 10 as Num
union all select  8 as ID, 15 as Num
union all select  9 as ID, 20 as Num
union all select 10 as ID, 25 as Num

Задано значение показателя, например 37.
Необходимо написать запрос, который вернет перчень ID показателей, сумма которых будет максимально близка к заданному.
Для 37 это один из вариантов: 7+10+20, то есть ID=4;7;9
1 сен 16, 18:19    [19618615]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
rsolanov,

это реальная задача или учеба?
1 сен 16, 18:39    [19618667]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
Mike_za
rsolanov,

это реальная задача или учеба?

Это реальная одна из подзадач связанная с поиском ID сделок, она сводится именно к этому. Я максимально все упростил, чтобы осталась только суть.
1 сен 16, 18:43    [19618685]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
crossjoin
Guest
declare @target int=37

;with cte as
(
select t1.ID ID1,t1.Num N1,t2.ID ID2,t2.Num N2 from #Numbers t1 cross join #Numbers t2
)
select ID,ID1,ID2,Num N,N1,N2,N1+N2+Num [Sum],abs(@target-(N1+N2+Num)) diff from cte
cross join #Numbers t3
order by abs(@target-(N1+N2+Num))
1 сен 16, 19:15    [19618773]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
Я похоже понял как надо сделать:
1. Фильтруем таблицу чтобы Num < @Value
2. Сортируем таблицу по полю Num по убыванию;
3. Берем первый элемент, самое большое значение Num (получили ID)
4. Вычитаем: @Value = @Value - Num
5. Если @Value = 0 поиск завершен
5. Ищем по всем элементам оставшееся значение.
6. Если находим, поиск завершен (получили ID), если нет, продвигаемся на один элемент вперед
7. Если просмотрели все элементы, поиск завершен, если нет, переходим к пункту 3.

Но возможно можно и придумать более эффективный поиск.
1 сен 16, 22:15    [19619255]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
Завтра с утра напишу запрос
1 сен 16, 22:16    [19619258]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8350
rsolanov,

это задача упаковки рюкзака и она не решается средствами реляционной алгебры.
1 сен 16, 23:10    [19619435]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
Владислав Колосов
rsolanov,
это задача упаковки рюкзака и она не решается средствами реляционной алгебры.

Это и так всем понятно, но мне это необходимо реализвать в t-sql всего лишь как небольшая чать большой работы.
2 сен 16, 09:37    [19620052]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 31783
rsolanov
Я похоже понял как надо сделать:
1. Фильтруем таблицу чтобы Num < @Value
2. Сортируем таблицу по полю Num по убыванию;
3. Берем первый элемент, самое большое значение Num (получили ID)
4. Вычитаем: @Value = @Value - Num
5. Если @Value = 0 поиск завершен
5. Ищем по всем элементам оставшееся значение.
6. Если находим, поиск завершен (получили ID), если нет, продвигаемся на один элемент вперед
7. Если просмотрели все элементы, поиск завершен, если нет, переходим к пункту 3.
"5. Ищем по всем элементам оставшееся значение." - это рекурсивно, как для первого элемента?

И ещё, так можно найти элементы с точным соответствием по сумме. А если таких нету, то алгоритм нужно менять - для каждого начального элемента нужно запоминать сумму, а потом выбирать наиболее близкую.
2 сен 16, 10:11    [19620150]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
Пока для реализации этого алгоритма в голову приходят одни курсоры.
Буду благодарен если кто поможет написать реализацию этого алгоритма без курсоров.
5 сен 16, 10:16    [19627898]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
AnSi_Sr
Member

Откуда:
Сообщений: 134
rsolanov,

Такую задачу можно решить перебором всех возможные сочетаний элементов.
В Oracle технически это реализуется с помощью иерархических запросов вида connect by level <= число строк в таблице.
В MS SQL тоже есть что-то похожее.
5 сен 16, 10:32    [19627946]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
iljy
Member

Откуда:
Сообщений: 8711
rsolanov,

if object_id('tempdb..#Numbers') is not null
	drop table #Numbers
create table #Numbers
(
	ID  int,
	Num int
)

insert into #Numbers
		  select  1 as ID,  3 as Num
union all select  2 as ID,  5 as Num
union all select  3 as ID,  2 as Num
union all select  4 as ID,  7 as Num
union all select  5 as ID,  1 as Num
union all select  6 as ID,  8 as Num
union all select  7 as ID, 10 as Num
union all select  8 as ID, 15 as Num
union all select  9 as ID, 20 as Num
union all select 10 as ID, 25 as Num

declare @trg int = 37
;with cte as
(
	select ID maxid, CAST(ID as varchar(max)) ids, Num s from #Numbers where Num < @trg
		union all
	select n.id, ids + ',' + CAST(ID as varchar(max)), s + n.Num
	from cte c join #Numbers n on n.id > maxid and s + n.Num <= @trg
)
select ids, s 
from cte
order by @trg - s 
5 сен 16, 10:40    [19627985]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
iljy,
у меня пока вот что получилось:
if object_id('tempdb..#Numbers') is not null
	drop table #Numbers
create table #Numbers
(
	ID  int,
	Num int
)

insert into #Numbers
		  select  1 as ID,  3 as Num
union all select  2 as ID,  5 as Num
union all select  3 as ID,  2 as Num
union all select  4 as ID,  7 as Num
union all select  5 as ID,  1 as Num
union all select  6 as ID,  8 as Num
union all select  7 as ID, 10 as Num
--union all select  8 as ID, 12 as Num
union all select  9 as ID, 15 as Num
union all select 10 as ID, 20 as Num
union all select 11 as ID, 25 as Num

declare
	@Value int = 37

if object_id('tempdb..#Results') is not null
	drop table #Results
create table #Results
(
	ID  int,
	Num int
)

declare
	@ID int,
	@Num int,
	@ID2 int,
	@Num2 int,
	@Rest int,
	@lb_Exit bit

declare Numbers cursor fast_forward for
select 
	* 
from 
	#Numbers as nums
where
	Num <= @Value
order by
	Num desc

open Numbers           
fetch next from Numbers into @ID, @Num --3-й п.

set @Rest = @Value
set @lb_Exit = 0

while @@FETCH_STATUS = 0 and @lb_Exit = 0        
begin
	if (@Num <= @Rest)
	begin
		insert into #Results (ID, Num) values (@ID, @Num)

		set @Rest = @Rest - @Num
		if @Rest = 0 set @lb_Exit = 1

		select top 1 @ID2 = ID, @Num2 = Num from #Numbers where Num = @Rest
		if @ID2 is not null
		begin
			insert into #Results (ID, Num) values (@ID2, @Num2)
			set @lb_Exit = 1
		end
		--select @ID as ID, @Num as Num, @Value as Vale, @Rest as Rest, @lb_Exit as lb_Exit
	end
	fetch next from Numbers into @ID, @Num--3-й п.
end

close Numbers          
deallocate Numbers

select * from #Results

GO
5 сен 16, 11:13    [19628144]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
iljy
Member

Откуда:
Сообщений: 8711
rsolanov,

я не понял, вы жалуетесь или хвастаетесь? 8) В моем решении что-то не так?
5 сен 16, 11:15    [19628160]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
Да, iljy, прошу прощения, сразу не поблагодарил вас. Спасибо вам за помощь, сейчас постараюсь на основе предложенного вами решения сделать запрос который вернет набор данных такой же, какой генерирует мой код. То есть необходимо получить первое решение с минимальным набором ID, сумма Num которых максимально близка к @trg
5 сен 16, 11:23    [19628194]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
iljy
Member

Откуда:
Сообщений: 8711
rsolanov,

максимально близка - в том числе сверху? тогда надо немного ослабить условия - убрать отбор в корне рекурсии и ослабить в соединении (заменить на s < @trg)
5 сен 16, 11:31    [19628247]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
iljy
Member

Откуда:
Сообщений: 8711
rsolanov,

а, ну и order by ABS(@trg - s).
5 сен 16, 11:33    [19628255]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
iljy, также если задать @trg = 25 ваш запрос не вернет вариант с единственным ID=10
5 сен 16, 11:35    [19628267]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
то есть если задать @trg = 25 то по условию задачи ответ должен быть однозначным это ID=10 (минимальный набор ID, сумма максимально близка к @trg)
5 сен 16, 11:41    [19628292]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
iljy
Member

Откуда:
Сообщений: 8711
rsolanov,

поправьте условие в корне рекурсии.

по поводу минимального набора - не было такого уговора. Если нужно, то добавьте в рекурсию и сортировку счетчик количества ИД.
5 сен 16, 12:08    [19628387]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
iljy, можно переписать ваш запрос таким образом, чтобы он выдавал не строки с id через запятую, а id раскладывал в строки с указанием группы (в новой колонке)?
5 сен 16, 12:22    [19628425]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
iljy
Member

Откуда:
Сообщений: 8711
rsolanov,


не вопрос. собирайте не через запятую, а в виде xml, а дальше его распарсите.
5 сен 16, 12:33    [19628479]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
Вот что у меня вчера получилось:
if object_id('tempdb..#Numbers') is not null
	drop table #Numbers
create table #Numbers
(
	ID  int,
	Num int
)

insert into #Numbers
select  1 as ID,  3 as Num
union all select  2 as ID,  5 as Num
union all select  3 as ID,  2 as Num
union all select  4 as ID,  7 as Num
union all select  5 as ID,  13 as Num
union all select  6 as ID,  8 as Num
union all select  7 as ID, 10 as Num
--union all select  8 as ID, 12 as Num
union all select  9 as ID, 15 as Num
union all select 10 as ID, 20 as Num
union all select 11 as ID, 25 as Num


declare @Value int = 39

;with 
Numbers as
(
	select 
		*,
		row_number() over (order by Num asc) as Rn
	from
		#Numbers
)
, cte as
(
	select 
		Rn as MaxRn, 
		'<item>' + CAST(ID as varchar(max)) + '</item>' as IDs, 
		Num as s, 
		1 as [Level]
	from Numbers where Num <= @Value 
		union all
	select 
		n.Rn, 
		IDs + '<item>' + CAST(ID as varchar(max)) + '</item>', s + n.Num, 
		1 + [Level]
	from 
			cte 
		inner join 
			Numbers n on 
			n.rn > cte.MaxRn and cte.s <= @Value
)
select
	Data.ID,
	Nums.Num,
	Data.s as Summa
from
		(
			select
				t.n.value('.', 'nvarchar(20)') as ID,
				s
			from
					(
						select top 1 
							cast(IDs as xml), 
							s
						from
							cte
						where
							cte.s in (
								select
									min(s) as s
								from
									cte as cte_outer
								where
									cte_outer.s >= @Value
							)
						order by
							[Level]
					) as Data(IDs, s)
				cross apply 
					IDs.nodes('item') as t(n)
		) as Data
	inner join
		#Numbers as Nums on
		Nums.ID = Data.ID
6 сен 16, 09:44    [19631493]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
iljy
Member

Откуда:
Сообщений: 8711
rsolanov,

а че у вас в основном запросе какие-то дикие подзапросы? вы чего получить ими хотели?
6 сен 16, 10:33    [19631720]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос: поиск оптимального решения  [new]
rsolanov
Member

Откуда:
Сообщений: 930
iljy, в техническом задании оказались моменты которые не сразу были известны, например пришлось добавить условие:
where
		cte.s in (
			select
				min(s) as s
			from
				cte as cte_outer
			where
				cte_outer.s >= @Value
		)

сейчас все протестировали на псевдоданных, все работает как надо )
6 сен 16, 11:12    [19631948]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить