quote:

---

Originally posted by Peso

You spent 1 hour, 13 minutes and 33 seconds to find it?
Impressive!


Peter Larsson
Helsingborg, Sweden

---

quote:

---

Originally posted by maya_zakry

ohh KHTAN...
before i start reading the post.. would like to thank u first..
peso! and u spent sometime to count on the time! :P

~~~Focus on problem, not solution~~~

---

-- Initialize the search parameter
DECLARE	@WantedValue INT

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

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