SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 General SQL Server Forums
 Script Library
 Sum up an unknown number of records
 New Topic  Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

SwePeso
Patron Saint of Lost Yaks

Sweden
30250 Posts

Posted - 03/19/2007 :  19:11:21  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Edited by - SwePeso on 03/19/2007 20:18:32

SwePeso
Patron Saint of Lost Yaks

Sweden
30250 Posts

Posted - 03/19/2007 :  19:17:23  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Edited by - SwePeso on 03/19/2007 19:18:36
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30250 Posts

Posted - 03/19/2007 :  19:23:07  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Edited by - SwePeso on 03/19/2007 19:31:27
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30250 Posts

Posted - 03/19/2007 :  19:39:03  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Edited by - SwePeso on 08/12/2008 10:36:09
Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.09 seconds. Powered By: Snitz Forums 2000