Sum up an unknown number of records

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

General SQL Server Forums

Script Library

Sum up an unknown number of records

Author

Topic

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-03-19 : 19:11:21

With this algorithm you can sum up an unkown number of records, so that an aggregation matches a fixed value.
If there is not an exakt match available, the algorithm returns the nearest possible value!

-- Initialize the search parameter
DECLARE	@WantedValue INT

SET	@WantedValue = 349

-- 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 productsum is less than or equal to the wanted sum, select all items!
IF (SELECT SUM(MaxItems * FaceValue) FROM @Data) <= @WantedValue
	BEGIN
		SELECT	MaxItems AS Items,
			FaceValue
		FROM	@Data

		RETURN
	END

-- Delete all unworkable FaceValues 
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	BestUnder AS Items,
			FaceValue
		FROM	@Data
		WHERE	BestUnder > 0
	ELSE
		-- If BestOver is closer to the sum we want, choose that
		SELECT	BestOver AS Items,
			FaceValue
		FROM	@Data
		WHERE	BestOver > 0
ELSE
	-- We have an exact match
	SELECT	CurrentItems AS Items,
		FaceValue
	FROM	@Data
	WHERE	CurrentItems > 0

With references to
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=73540
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=73610
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=78015
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=79505

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-03-19 : 19:17:23

This is the part you need to change to fit your environment

-- Aggregate the source data
INSERT		@Data
		(
			MaxItems,
			FaceValue
		)
SELECT		COUNT(*),
		{YourColumnNameHere}
FROM		{YourTableNameHere}
GROUP BY	{YourColumnNameHere}
ORDER BY	{YourColumnNameHere} DESC

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-03-19 : 19:23:07

If you want to know if it's an UnderSum or an OverSum returns, change this place

-- If productsum is less than or equal 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 (SELECT SUM(MaxItems * FaceValue) FROM @Data) = @WantedValue
	BEGIN
		SELECT	0 AS SumType,
			MaxItems AS Items,
			FaceValue
		FROM	@Data

		RETURN
	END

And this place in algorithm

-- 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

If you do these changes, you can see that a negative SumType denotes an UnderSum in return, a positive value for SumType denotes an OverSum returned and at last a zero SumType denotes an exakt match!

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-03-19 : 19:39:03

Here is how the algorithm looks like with all implementation described above

-- Initialize the search parameter
DECLARE	@WantedValue INT

SET	@WantedValue = 349

-- 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(*),
		{YourColumnNameHere}
FROM		{YourTableNameHere}
GROUP BY	{YourColumnNameHere}
ORDER BY	{YourColumnNameHere} 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

Peter Larsson
Helsingborg, Sweden

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources