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

DECLARE @Source TABLE (Id INT, Value DECIMAL(19,2));

INSERT @Source 
VALUES (21312, 16),
       (7813412, 17),
       (321312, 9),
       (5612, 15),
       (90312, 5),
       (172, 6),
       (3612, 8),
       (9812, 7);


DECLARE @RequestSum DECIMAL(19,2) = 30;


Нужно выбрать записи, чтобы сумма выбранных значений была максимально близка к требуемой (RequestSum).

Я делал обратную сортировку по значению и в цикле собирал сумму:
17 + 15 (превышение - пропускаем) + 9 + 8 (превышение - пропускаем)....
Получил 26.
Но 9 + 8 + 7 + 6 = 30 - лучше.

Какой алгоритм сделать? Нужно что то типа массива? Но строк может быть много - динамику?

Или лучше создать CLR том же C#?
14 мар 18, 17:01    [21256274]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм набора указанной суммы из списка чисел  [new]
msLex
Member

Откуда:
Сообщений: 7726
https://ru.wikipedia.org/wiki/Задача_о_ранце

https://www.sql.ru/forum/afsearch.aspx?s=??????_?_?????&submit=?????&bid=1
14 мар 18, 17:32    [21256421]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм набора указанной суммы из списка чисел  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6794
Pochemoochka,

тем действительно масса... самый общий наверное

а как вам выбирать из массы результатов это другой вопрос
;WITH xxx AS
(
	SELECT 
		Id as xId, CAST(Value as float) as Summ,
		Line = CAST(Value as varchar(max)) 
	FROM @Source 
	WHERE 
		Value <= @RequestSum
	UNION ALL
	SELECT 
		b.Id as xId,
		a.Summ + b.Value ,
		Line + ' + ' + CAST(Value as varchar(max)) 
	FROM xxx		a
	INNER JOIN	@Source b
	ON
		b.Id > a.xId	AND
		a.Summ + b.Value  <= @RequestSum
	
)
SELECT TOP 1 WITH TIES
	Line,
	Summ
FROM xxx a
ORDER BY Summ DESC
14 мар 18, 17:51    [21256495]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм набора указанной суммы из списка чисел  [new]
Pochemoochka
Guest
TaPaK,

Спасибо! Самое то.
15 мар 18, 09:02    [21257499]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить