We help IT Professionals succeed at work.

Aggregate /MAX SQL / probability?

Dear Experts,

I wanted to calculate the sum from a set of values - contributing to maximum possible sum value less than an absolute number in SQL.

Example:
I have a set of 5 values : 800,350,260,250,300

I want to sum up the values from the above set to get a value closest to 1000 not exceeding it.

like 350+260+300 will sum upto 910 which is the best max possible value. I want to put this in an algorithm

Please help
Comment
Watch Question

Billing Engineer
Most Valuable Expert 2014
Top Expert 2009
Commented:
please check out this code sample to get you started:
you shall need to add more "left joins" and "WHEN" statements, but you get the figure ...
DECLare @t table ( v int )
insert into @t (v) values (800)
insert into @t (v) values (350)
insert into @t (v) values (260)
insert into @t (v) values (250)
insert into @t (v) values (300)

declare @threshold int
set @threshold = 1000

;with data as (
select t1.v v1, t2.v v2, t3.v v3 , t4.v v4
 , case 
   when t1.v + t2.v + t3.v + t4.v <= @threshold then t1.v + t2.v + t3.v + t4.v
   when t1.v + t2.v + t3.v <= @threshold then t1.v + t2.v + t3.v
   when t1.v + t2.v <= @threshold then t1.v + t2.v 
   when t1.v <= @threshold then t1.v 
   else 0 end t
 , case 
   when t1.v + t2.v + t3.v + t4.v <= @threshold then 3
   when t1.v + t2.v + t3.v <= @threshold then 3
   when t1.v + t2.v <= @threshold then 2
   when t1.v <= @threshold then 1
   else 0 end taken
from @t t1
left join @t t2
  on t2.v <> t1.v
left join @t t3
  on t3.v <> t1.v
 and t3.v <> t2.v
left join @t t4
  on t4.v <> t1.v
 and t4.v <> t2.v
 and t4.v <> t3.v
)
select * 
  from data
where t <= @threshold
order by t desc

Open in new window

Author

Commented:
i understand it is something to do with analytical queries.. will wait for a day or two before closing .. thanks
Commented:
Give this a shot. I thought it was an interesting problem, so I tried to design a quick solution to allow for an dynamic number of values. It might not be the most efficient method; I'm sure somebody else might be able to refine the code (i.e. CTEs, or CROSS JOINS).

If one had to draw out a decision tree; it would be n values deep (where n is the number of elements), with 2 (i.e. the actual value or 0) possibilities for each branch. Conceptually something like this:
                    350  
           800 /
Start /        \ 0
        \          350  
           0    /
                 \ 0

So on and so forth; so for n values, given that you have 2 (value or 0) permutations for each value - you would have 2^n combinations (in this case 2^5 = 32)

The SQL simply creates the 2^n records in a temp table, and iteratively updates the values to create a table representation of the decision tree.

I only have the final result; but the @ResultTable table is available for more querying if you need to figure out which set of numbers made up the max sum.

Hope this helps.

DECLARE		@ValueTable table ([ID] int NOT NULL, [Val] int NOT NULL)
DECLARE		@ResultTable table ([ID] int NOT NULL, CombinationId int NOT NULL, ValueIndex int NOT NULL, [Val] int)
DECLARE	
	@NumberOfValues int,
	@TotalCombinations int,
	@i int,
	@Treshold int

INSERT INTO @ValueTable ([ID], [Val])
-- Add the values here
SELECT 1, 800 UNION
SELECT 2, 350 UNION
SELECT 3, 260 UNION
SELECT 4, 250 UNION
SELECT 5, 300 
-- UNION SELECT 6, 70

SELECT @NumberOfValues = COUNT([ID]) FROM @ValueTable

-- Initialize Variables
SELECT	
	@i = POWER(2, @NumberOfValues) * @NumberOfValues,
	@Treshold = 1000

-- Add records to @ResultTable for all possible combinations
WHILE @i > 0
BEGIN
	INSERT INTO @ResultTable ([ID], [CombinationId], [ValueIndex], [Val])
	SELECT @i, (@i - 1) / @NumberOfValues + 1, @i % @NumberOfValues + 1, NULL

	SELECT @i = @i - 1
END

-- Loop through each value to update @ValueTable.[val] field
SELECT @i = MIN([ID]) FROM @ValueTable
SELECT @TotalCombinations = MAX(CombinationId) FROM @ResultTable

WHILE @i < @NumberOfValues + 1
BEGIN
	UPDATE @ResultTable 
	SET
		[Val] = (SELECT [Val] FROM @ValueTable WHERE [ID] = @i)
	WHERE
		ValueIndex = @i AND	
		((CombinationId - 1)/ (@TotalCombinations / POWER(2, @i))) % 2 = 0 -- Even ones only

	UPDATE @ResultTable 
	SET
		[Val] = 0
	WHERE
		ValueIndex = @i AND	
		((CombinationId - 1)/ (@TotalCombinations / POWER(2, @i))) % 2 = 1 -- Odd ones only
	
	SELECT @i = @i + 1
END

-- Calculate max sum < @Treshold
SELECT MAX([Summation])
FROM
	(SELECT	CombinationId, SUM([Val]) As Summation FROM @ResultTable GROUP BY CombinationId HAVING SUM([Val]) < @Treshold) A

Open in new window

Commented:
One more thing, when I put resultset in Excel pivottable - this is what I get (see attached screenshot). Should provide a visual of what the algorithm is doing.
Screenshot.JPG
Screenshot-6Values.JPG

Author

Commented:
I've requested that this question be deleted for the following reason:

Dear Experts, Basically i couldn't try the solutions provided. And no more i need to work on this as of now. hence requesting to delete the question. Thanks.

Commented:
This should have been communicated before anybody worked on this, or results of whether solutions did not work should have been posted. As of my review, these solutions work and should be able to help others in similar questions.