| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Очередные извращения в TSql
Павел Калугин © (2007-06-18 16:01:00)дано
таблица
Актив | Цена
-------------------
1 | 10
2 | 50
3 | 150
4 | 300
Собрать все вохможные комбинации активов не преввышающие по стоимости sum(цена)
и получить данные вида
ID комб. | Актив | Кол-во
то есть ограничение по сумме 510
Некоторые возможные комбинации
3*1, 4*1,...,51*1
1*1+2*1+3*1+4*1
4+3+1
то есть получаем
X*1+Y*2+Z*3*K*4 <=510
и как это можно сделать запросом?
и как вообще это можно алгоритмизировать?
Павел Калугин (2007-06-19 12:52:00) [1]Спасибо за подсказки.
Есть большпая надежда что 10 не перевалит.
еще большая - что дальше тестовой версии и не пойдет... мечты мечты...
Johnmen (2007-06-19 12:14:00) [2]И ещё....
Если есть ограничение по сумме (судя по [0]), то алгоритм можно фантастически оптимизировать.
Короче, надо терию почитать. На тему "оптимизация целевой функции".
Johnmen (2007-06-19 12:08:00) [3]
> но куда на эту тему смотреть не знаю
Смотри в Яндекс/Гугль. По-другому "хвостовая рекурсия".
Твоя задача легко разворачивается в цикл. Но имей в виду, что время обработки с увеличением кол-ва записей будет расти экспоненциально. И при кол-ве Активов порядка 50 ты устанешь ждать окончания. А при порядка 100 не дождешься никогда...:)
clickmaker (2007-06-19 11:44:00) [4]
> рекурсию всегда можео преобразовать в цикл
см. Expanding Hierarchies в MS SQL Books Online
Павел Калугин (2007-06-19 11:23:00) [5]Попробовал вчера этот путь. Наступил на ограничение вложенности вызова. 32 раза и все... боле нельзя
alter procedure sp_test_komb
@sum money = null
as
begin
if @sum is null
set @sum = (select sum(price) from #test)
print 'summa: '+convert(varchar,@sum)
declare @i int
declare @var varchar(255)
set @i=0
while @i<(select count(id) from #test)
begin
set @i=@i+1
if @sum-(select price from #test where id = @i) < 0
begin
set @var=''
select @var=@var+convert(varchar,qty)+'; ' from #test --order by 1
set @var = convert(varchar,@i)+'; '+@var
print @var
end
else begin
declare @sum2 money
update #test set qty = qty + 1 where id = @i
set @sum2 = @sum-(select price from #test where id = @i)
exec sp_test_komb @sum2
update #test set qty = qty - 1 where id = @i
end
end
end
go
set nocount on
create table #test(id int,price int,qty int)
insert into #test (id,price,qty)values(1,50,0)
insert into #test (id,price,qty)values(2,150,0)
insert into #test (id,price,qty)values(3,200,0)
insert into #test (id,price,qty)values(4,4000,0)
exec sp_test_komb
drop table #test
Прозвучала фраза "концевую рекурсию всегда можео преобразовать в цикл"
но куда на эту тему смотреть не знаю
Johnmen (2007-06-18 19:11:00) [6]Не откладывай на завтра то, что можно сделать послезавтра! (с)
Появилось своб.время.
Итак. Пишешь ничем не примечательную обычную рекурсивную процедуру.
Парметры (<текущий список IDАктивов>,<текущий IDАктива>,<текущая сумма Цен>).
Результат работы - временная таблица или возвращаемый НД с такими данными:
1,2,3,4 | 510
1,2,3 | 210
1,2,4 | 360
1,3,4 | 460
1,3 | 160
1,4 | 310
1 | 10
2,3,4 | 500
2,3 | 200
2,4 | 350
2 | 50
3,4 | 450
3 | 150
4 | 300
Johnmen (2007-06-18 17:56:00) [7]Домой пора. Завтра скажу....:)
Павел Калугин (2007-06-18 17:54:00) [8]так понятно что ХП.
вопрос в том, как ее писать, чтобы при изменении кол-ва записей в исходной таблице не менять текст ХП
Johnmen (2007-06-18 17:50:00) [9]Я бы написал ХП....
Павел Калугин (2007-06-18 17:46:00) [10]предположить что в какой то момент времени два актива сравняются по цене да это возможно. Маловероятно но рынок, значит возможно
Johnmen (2007-06-18 17:40:00) [11]Так можно на это закладываться или нет?
Павел Калугин (2007-06-18 17:36:00) [12]Могут но маловероятно. Рынок....
Johnmen (2007-06-18 16:32:00) [13]Могут быть разные Активы с одинаковой ценой?
Павел Калугин (2007-06-18 16:03:00) [14]4 вложенных цикла от 0 до sum/цена?
а завтра это буждет 10 активов? код переписывать?
| |
