Peter Larsson Blog

Patron Saint of Lost Yaks

How to sum up an unknown number of records

by Peter Larsson in  , , , ,

– Initialize the search parameter
DECLARE       @WantedValue INT  
SET    @WantedValue = 221
 
– Stage the source data
DECLARE       @Data TABLE
       (
              RecID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
              MaxItems INT,
              CurrentItems INT DEFAULT 0,
              FaceValue INT,
              BestUnder INT DEFAULT 0,
              BestOver INT DEFAULT 1
       )
 
– Aggregate the source data
INSERT        @Data
              (
                     MaxItems,
                     FaceValue
              )
SELECT        COUNT(),
              Qty
FROM          (
                     SELECT 899 AS Qty UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 95 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 55 UNION ALL
                     SELECT 40 UNION ALL
                     SELECT 5 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 250 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 90 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 350 UNION ALL
                     SELECT 450 UNION ALL
                     SELECT 450 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 1 UNION ALL
                     SELECT 10 UNION ALL
                     SELECT 1
              ) AS d
GROUP BY      Qty
ORDER BY      Qty DESC
 
 
– Declare some control variables
DECLARE       @CurrentSum INT,
       @BestUnder INT,
       @BestOver INT,
       @RecID INT
 
– If exact single wanted sum, select that item!
IF EXISTS (SELECT FROM @Data WHERE FaceValue = @WantedValue)
       BEGIN
              SELECT 0 AS SumType,
                     1 AS Items,
                     FaceValue
              FROM   @Data
              WHERE FaceValue = @WantedValue
 
              RETURN
       END
 
– If productsum is less to the wanted sum, select all items!
IF (SELECT SUM(MaxItems FaceValue) FROM @Data) < @WantedValue
       BEGIN
              SELECT -1 AS SumType,
                     MaxItems AS Items,
                     FaceValue
              FROM   @Data
 
              RETURN
       END
 
– If productsum is equal to the wanted sum, select all items!
IF (SELECT SUM(MaxItems FaceValue) FROM @Data) = @WantedValue
       BEGIN
              SELECT 0 AS SumType,
                     MaxItems AS Items,
                     FaceValue
              FROM   @Data
 
              RETURN
       END
 
– Delete all unworkable FaceValues, keep one greater FaceValue because of oversum.
DELETE
FROM   @Data
WHERE FaceValue > (SELECT MIN(FaceValue) FROM @Data WHERE FaceValue >= @WantedValue)
 
– Update MaxItems to a proper value
UPDATE @Data
SET    MaxItems =    CASE
                           WHEN 1 + (@WantedValue - 1) / FaceValue < MaxItems THEN 1 + (@WantedValue - 1) / FaceValue
                           ELSE MaxItems
                     END
 
– Update BestOver to a proper value
UPDATE @Data
SET    BestOver = MaxItems
 
– Initialize the control mechanism
SELECT @RecID = MIN(RecID),
       @BestUnder = 0,
       @BestOver = SUM(BestOver FaceValue)
FROM   @Data
 
– Do the loop!
WHILE @RecID IS NOT NULL
       BEGIN
              – Reset all "bits" not incremented
              UPDATE @Data
              SET    CurrentItems = 0
              WHERE RecID < @RecID
 
              – Increment the current "bit"
              UPDATE @Data
              SET    CurrentItems = CurrentItems + 1
              WHERE RecID = @RecID
 
              – Get the current sum
              SELECT @CurrentSum = SUM(CurrentItems FaceValue)
              FROM   @Data
              WHERE CurrentItems > 0
 
              – Stop here if the current sum is equal to the sum we want
              IF @CurrentSum = @WantedValue
                     BREAK
              ELSE
                     – Update the current BestUnder if previous BestUnder is less
                     IF @CurrentSum > @BestUnder AND @CurrentSum < @WantedValue
                            BEGIN
                                  UPDATE @Data
                                  SET    BestUnder = CurrentItems
 
                                  SET    @BestUnder = @CurrentSum
                           END
                     ELSE
                           – Update the current BestOver if previous BestOver is more
                           IF @CurrentSum > @WantedValue AND @CurrentSum < @BestOver
                                  BEGIN
                                         UPDATE @Data
                                         SET    BestOver = CurrentItems
 
                                         SET    @BestOver = @CurrentSum
                                  END
 
              – Find the next proper "bit" to increment
              SELECT @RecID = MIN(RecID)
              FROM   @Data
              WHERE CurrentItems < MaxItems
       END
 
– Now we have to investigate which type of sum to return
IF @RecID IS NULL
       IF @WantedValue - @BestUnder < @BestOver - @WantedValue
              – If BestUnder is closer to the sum we want, choose that
              SELECT -1 AS SumType,
                     BestUnder AS Items,
                     FaceValue
              FROM   @Data
              WHERE BestUnder > 0
       ELSE
              – If BestOver is closer to the sum we want, choose that
              SELECT 1 AS SumType,
                     BestOver AS Items,
                     FaceValue
              FROM   @Data
              WHERE BestOver > 0
ELSE
       – We have an exact match
       SELECT 0 AS SumType,
              CurrentItems AS Items,
              FaceValue
       FROM   @Data
       WHERE CurrentItems > 0

Legacy Comments
Ram
2008-08-21		 re: How to sum up an unknown number of records
Hi, What you are doing here? if we give a number, you are expressing it as sum of items with some
multiplications according to number of items. if i enter a number 508, it is not returning the correct sum. although its not possible to return 508 from that one. it has to give message. but it is displaying worng sum.
I worked now. i am submitting my solution. please look this and give your review.

declare @ReqNumber int
set @ReqNumber = 510

DECLARE @Data TABLE
(
RecID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
MaxItems INT,
CurrentItems INT DEFAULT 0,
FaceValue INT,
BestUnder INT DEFAULT 0,
BestOver INT DEFAULT 1
)

-- Aggregate the source @Data
INSERT @Data
(
MaxItems,
FaceValue
)
SELECT COUNT(*),
Qty
FROM (
SELECT 899 AS Qty UNION ALL
SELECT 100 UNION ALL
SELECT 95 UNION ALL
SELECT 50 UNION ALL
SELECT 55 UNION ALL
SELECT 40 UNION ALL
SELECT 5 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 50 UNION ALL
SELECT 250 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 90 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 50 UNION ALL
SELECT 350 UNION ALL
SELECT 450 UNION ALL
SELECT 450 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 50 UNION ALL
SELECT 50 UNION ALL
SELECT 50 UNION ALL
SELECT 1 UNION ALL
SELECT 10 UNION ALL
SELECT 1
) AS d
GROUP BY Qty
ORDER BY Qty DESC
declare @BigNumber int
declare @Iterations int
declare @temp table
(
MaxItems int,
FaceValue int
)
while(@ReqNumber > 0 )
begin

set @BigNumber = (select max(FaceValue) from @Data where FaceValue <= @ReqNumber and FaceValue not in (select FaceValue from @temp))
if(@BigNumber is null)
begin
select 'Its Not Possible'
break;
end
set @Iterations = @ReqNumber / @BigNumber
if(@Iterations > (select MAxItems from @Data where FaceValue = @BigNumber))
set @Iterations = (select MAxItems from @Data where FaceValue = @BigNumber)
insert into @temp values (@Iterations,@BigNumber)
set @ReqNumber = @ReqNumber - (@Iterations * @BigNumber)
if(@ReqNumber = 0)
begin
select * from @temp
break;
end
end
Ram
2008-08-22		 re: How to sum up an unknown number of records
Hi, What you are doing here?
if we give a number, you are expressing it as
sum of items with some multiplications according to number of items. if i enter a number 508, it is not returning the correct sum. although its not possible to return 508 from that one. it has to give message. but it is displaying worng sum.
I worked now. i am submitting my solution. please look this and give your review.
Peso
2008-08-22		 re: How to sum up an unknown number of records
You have missed the whole point!
If no correct sum is found, the NEAREST sum that is less or the NEAREST sum
that is more than the wanted sum is returned.
That is what SumType is telling you.

-1 means No correct sum is found, the nearest sum that is less is returned.
0 means Correct sum is found
+1 means No correct sum is found, the nearest sum that is more is returned.
Peso
2008-11-23		 re: How to sum up an unknown number of records
New faster algorithm found here
http://weblogs.sqlteam.com/peterl/archive/2008/11/23/Bin-packaging.aspx