Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Решение задачи минимума (максимума)  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 12
Добрый день!

Есть переменная
declare @Sum int = 20;


Есть таблица
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, при этом число записей будет минимально.

Ожидаемый результат:
id
3
4
6
7

Вопрос: как должен выглядеть запрос, абстрагируясь от значения
@Sum
и значений поля
value
?

Спасибо!
8 май 18, 16:07    [21396285]     Ответить | Цитировать Сообщить модератору
 Re: Решение задачи минимума (максимума)  [new]
Ennor Tiegael
Member

Откуда:
Сообщений: 3141
Гуглить задачу о ранце / рюкзаке. В т.ч. и на этом форуме.
8 май 18, 16:27    [21396334]     Ответить | Цитировать Сообщить модератору
 Re: Решение задачи минимума (максимума)  [new]
court
Member

Откуда:
Сообщений: 1956
вариант "в лоб" или "дай серверу погреться" :)

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
9 май 18, 08:18    [21397365]     Ответить | Цитировать Сообщить модератору
 Re: Решение задачи минимума (максимума)  [new]
court
Member

Откуда:
Сообщений: 1956
court
"дай серверу погреться" :)
кстате, имхо тот случай, когда стоит "вспомнить" про рекурсию аля СКЛ2000
имхо, будет "более лучше" ... :)

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
9 май 18, 09:09    [21397423]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить