Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Решение задачи минимума (максимума) / 4 сообщений из 4, страница 1 из 1
08.05.2018, 16:07
    #39642103
Leo Лапыч
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение задачи минимума (максимума)
Добрый день!

Есть переменная
Код: sql
1.
declare @Sum int = 20;



Есть таблица
Код: sql
1.
2.
declare @Table table(id int, value int);
insert into @Table values (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7);



Есть задача: выбрать из таблицы только те записи, сумма значений которых будет наиболее близка к значению @Sum, при этом число записей будет минимально.

Ожидаемый результат:
Код: plaintext
1.
2.
3.
4.
id
3
4
6
7

Вопрос: как должен выглядеть запрос, абстрагируясь от значения
Код: sql
1.
@Sum

и значений поля
Код: sql
1.
value

?

Спасибо!
...
Рейтинг: 0 / 0
08.05.2018, 16:27
    #39642111
Ennor Tiegael
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение задачи минимума (максимума)
Гуглить задачу о ранце / рюкзаке. В т.ч. и на этом форуме.
...
Рейтинг: 0 / 0
09.05.2018, 08:18
    #39642269
court
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение задачи минимума (максимума)
вариант "в лоб" или "дай серверу погреться" :)

Код: 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.
declare @Table table(id int, value int);
insert into @Table values (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7);

declare @Sum int = 20;

;with cte as (
	select
		id
		,value 
		,S		=value 
		,x		=cast('<a id="'+cast(id as varchar)+'" value="'+cast(value as varchar)+'" />' as varchar(max))
		,lvl	=1	 
	from @Table
	where value<=@Sum
	
	union all
	
	select
		t.id 
		,t.value  
		,S		=t.value+cte.S   
		,x		=cte.x + '<a id="'+cast(t.id as varchar)+'" value="'+cast(t.value as varchar)+'" />'   
		,lvl	=cte.lvl+1	 
	from @Table t inner join cte on t.id>cte.id  
	where t.value+cte.S<=@Sum)
	
select top 1 
	x	=cast(x as xml) 
	,S 
from cte 	
order by @Sum-S, lvl 



xS<a id="3" value="3" /><a id="4" value="4" /><a id="6" value="6" /><a id="7" value="7" />20
...
Рейтинг: 0 / 0
09.05.2018, 09:09
    #39642273
court
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение задачи минимума (максимума)
court"дай серверу погреться" :)кстате, имхо тот случай, когда стоит "вспомнить" про рекурсию аля СКЛ2000
имхо, будет "более лучше" ... :)

Код: 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.
declare @Table table(id int, value int);
insert into @Table values (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7);

declare @Sum int = 20;

declare @Result table (id int, S int, x varchar(max), lvl int)

insert into @Result
select 
	id
	,value
	,'<a id="'+cast(id as varchar)+'" value="'+cast(value as varchar)+'" />'
	,1
from @Table
where value<=@Sum

--
while not exists(select 1 from @Result where S=@Sum)
begin
	insert into @Result
	select
		t.id 
		,t.value+r.S   
		,r.x + '<a id="'+cast(t.id as varchar)+'" value="'+cast(t.value as varchar)+'" />'   
		,r.lvl+1	 
	from @Table t inner join @Result r on t.id>r.id  
	where t.value+r.S<=@Sum

	if @@rowcount=0 break
		
end	 

select top 1 
	x	=cast(x as xml) 
	,S 
from @Result  	
order by @Sum-S, lvl


xS<a id="2" value="2" /><a id="5" value="5" /><a id="6" value="6" /><a id="7" value="7" />20
...
Рейтинг: 0 / 0
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Решение задачи минимума (максимума) / 4 сообщений из 4, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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