ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Алгоритм набора указанной суммы из списка чисел
4 сообщений из 4, страница 1 из 1
Алгоритм набора указанной суммы из списка чисел
    #39614883
Pochemoochka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Pochemoochka
Гость
Имеем таблицу с суммами (любыми)

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
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#?
...
Рейтинг: 0 / 0
14.03.2018, 17:01
| Ответить | Цитировать | Написать  
Алгоритм набора указанной суммы из списка чисел
    #39614916
msLex
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
msLex
Участник
https://ru.wikipedia.org/wiki/Задача_о_ранце

http://www.sql.ru/forum/afsearch.aspx?s=??????_?_?????&submit=?????&bid=1
...
Рейтинг: 0 / 0
14.03.2018, 17:32
| Ответить | Цитировать | Написать  
Алгоритм набора указанной суммы из списка чисел
    #39614931
TaPaK
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
TaPaK
Участник
Pochemoochka,

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

а как вам выбирать из массы результатов это другой вопрос
Код: 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.
;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
...
Рейтинг: 0 / 0
14.03.2018, 17:51
| Ответить | Цитировать | Написать  
Алгоритм набора указанной суммы из списка чисел
    #39615170
Pochemoochka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Pochemoochka
Гость
TaPaK,

Спасибо! Самое то.
...
Рейтинг: 0 / 0
15.03.2018, 09:02
| Ответить | Цитировать | Написать  
4 сообщений из 4, страница 1 из 1
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Алгоритм набора указанной суммы из списка чисел
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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