Очередные извращения в TSql

← →
Павел Калугин © (2007-06-18 16:01) [0]

дано
таблица
Актив | Цена ------------------- 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-18 16:03) [1]

4 вложенных цикла от 0 до sum/цена?
а завтра это буждет 10 активов? код переписывать?

← →
Johnmen © (2007-06-18 16:32) [2]

Могут быть разные Активы с одинаковой ценой?

← →
Павел Калугин © (2007-06-18 17:36) [3]

Могут но маловероятно. Рынок....

← →
Johnmen © (2007-06-18 17:40) [4]

Так можно на это закладываться или нет?

← →
Павел Калугин © (2007-06-18 17:46) [5]

предположить что в какой то момент времени два актива сравняются по цене да это возможно. Маловероятно но рынок, значит возможно

← →
Johnmen © (2007-06-18 17:50) [6]

Я бы написал ХП....

← →
Павел Калугин © (2007-06-18 17:54) [7]

так понятно что ХП.
вопрос в том, как ее писать, чтобы при изменении кол-ва записей в исходной таблице не менять текст ХП

← →
Johnmen © (2007-06-18 17:56) [8]

Домой пора. Завтра скажу....:)

← →
Johnmen © (2007-06-18 19:11) [9]

Не откладывай на завтра то, что можно сделать послезавтра! (с)

Появилось своб.время.
Итак. Пишешь ничем не примечательную обычную рекурсивную процедуру.
Парметры (<текущий список 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

← →
Павел Калугин © (2007-06-19 11:23) [10]

Попробовал вчера этот путь. Наступил на ограничение вложенности вызова. 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

Прозвучала фраза "концевую рекурсию всегда можео преобразовать в цикл"
но куда на эту тему смотреть не знаю

> рекурсию всегда можео преобразовать в цикл

см. Expanding Hierarchies в MS SQL Books Online

> но куда на эту тему смотреть не знаю

Смотри в Яндекс/Гугль. По-другому "хвостовая рекурсия".
Твоя задача легко разворачивается в цикл. Но имей в виду, что время обработки с увеличением кол-ва записей будет расти экспоненциально. И при кол-ве Активов порядка 50 ты устанешь ждать окончания. А при порядка 100 не дождешься никогда...:)

И ещё....
Если есть ограничение по сумме (судя по [0]), то алгоритм можно фантастически оптимизировать.
Короче, надо терию почитать. На тему "оптимизация целевой функции".

Спасибо за подсказки.
Есть большпая надежда что 10 не перевалит.
еще большая - что дальше тестовой версии и не пойдет... мечты мечты...

Очередные извращения в TSql Найти похожие ветки