May 21, 2014 at 3:42 am
Hi everyone
Can someone help me with the follwing T-SQL problem:
I declare a local numeric variable:
declare @sum_to_find numeric(18,6)
set @sum_to_find = 4.8
Then I have a temp table, that contains some amounts (count of them is not known at design time)
What I want to achieve is the following:
I want to get the list of values, whose sum produce the value being seeked for (variable @sum_to_find)
The number of values producing the desired result may, of course, vary from 1 up to the total count of records in a temp table
CREATE TABLE #amounts
(recordIdinteger identity(1,1) primary key clustered,
amountnumeric(18,6) not null default 0);
insert into #amounts(amount) select 2.35 union all select 2.45 union all select 1.544 union all select 1.541 union all select 2.543 union all select 3.545
union all select 4.547 union all select 5.549 union all select 7.5413 union all select 8.5415 union all select 9.5417 union all select 1.44
union all select 1.1544 union all select 1.2974 union all select 1.3131 union all select 1.417134 union all select 1.521164 union all select 1.729224
union all select 1.833254 union all select 1.937284 union all select 2.5353 union all select 2.145344 union all select 2.249374 union all select 2.3534
select statement here....
In this particular case the records 1 and 2 fit into the search criteria.
I assume, a lot of processing can take place when there are hundreds of records.
I used some of my high school math (combinations without repetition, I guess) to figure out, at least, how many combinations there are to examine.
in this case id would be c24 1 + c242 + c243 + ... c2424
drop table #amounts
any help, tip is very much appreciated
Regards,
Mark
May 21, 2014 at 4:30 am
Mark
Here's a couple of ways to limit the amount of processing you need to do:
(1) Work out the maximum rows you need to consider.
If you put all the rows in order of amount and calculate a running total, you can make sure you limit your calculation to the smallest number of rows that can possibly sum to your target amount:
WITH Totals AS (
SELECT
ROW_NUMBER() OVER (ORDER BY amount) RowNo
,amount
FROM #amounts
)
SELECT
RunningTotal = SUM(b.amount)
,a.RowNo
FROM Totals a
JOIN Totals b ON b.RowNo <= a.RowNo
GROUP BY a.RowNo
In your example, you get this:
1.1544001
2.4518002
3.7649003
5.1820344
6.6220345
...
... and since your target is 4.8, you see that you don't need to consider more than three values.
(2) Exclude values that are greater than your target
Even simpler, this one:
SELECT COUNT(*) FROM #amounts
WHERE amount > 4.8
This returns 20, so there are four values you don't need to consider.
So, in your example, instead of considering up to 24 values out of 24, you're considering up to three rows out of 20.
John
May 21, 2014 at 5:07 am
John, thx for your reply.
What you say does help a lot. The problem hovewer remains.
I tried your solution in real life and it didn't help me much.
There are still more than 400 amounts left in the table. (the ones posted earlies on were just an example)
My real problem is the routine to get combinations of amounts that produce the same result.
Any ideas?
regards, Mark
May 21, 2014 at 5:54 am
Mark
I think your first problem is mathematical rather than programmatical. 400 values means 2^400 combinations, which is a much larger number than SQL Server can (as far as I know) handle precisely. There are probably algorithms out there that help you home in on the answer instead of finding it by brute force. I'm out of my depth on that, I'm afraid.
John
May 21, 2014 at 6:09 am
Thx again, John
What you say is true.
Guess I'll just have to use pure math algorythm first.
Many thanks.
Regards,
Mark
Viewing 5 posts - 1 through 4 (of 4 total)
You must be logged in to reply to this topic. Login to reply