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
 New to SQL Server Programming
 auto pick
 New Topic  Reply to Topic
 Printer Friendly
Next Page
Author Previous Topic Topic Next Topic
Page: of 2

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/21/2007 :  22:22:12  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote
hi all,
anyone has any idea in what i want to accomplish here :-
how can we sort the select statement, say, we want to compare integer inputqty=60.. how can we match the suitable sum of column qty to reach the 60 figure...

EG -> qty column : 50, 25, 15, 10

i)how can we prompt the select statemnet to choose 50 and 10 to make it 60...
ii)for another eg, say inputqty=90, then how can we prompt it to select 50 + 25 + 15 = 90
iii)and for some cases, if no round qty, the sum could be more, but the least from the qty list... eg : inputqty=80, how to automate the select statement to choose the closest figure, 50 + 25 + 10 = 85

i dunno if this is possible for any select or function or sp...
thankss....

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

khtan
In (Som, Ni, Yak)

Singapore
17681 Posts

Posted - 02/21/2007 :  22:34:14  Show Profile  Reply with Quote
I remember just sometime back, there is a similar question and Peter provided the solution. Can't seems to find it now. Don't worry, The Saint will comes to the rescue soon.


KH

Go to Top of Page

khtan
In (Som, Ni, Yak)

Singapore
17681 Posts

Posted - 02/21/2007 :  23:47:47  Show Profile  Reply with Quote
found it. See http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=78015



KH

Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30281 Posts

Posted - 02/22/2007 :  00:44:49  Show Profile  Visit SwePeso's Homepage  Reply with Quote
You spent 1 hour, 13 minutes and 33 seconds to find it?
Impressive!


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

khtan
In (Som, Ni, Yak)

Singapore
17681 Posts

Posted - 02/22/2007 :  01:31:01  Show Profile  Reply with Quote
quote:
Originally posted by Peso

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


Peter Larsson
Helsingborg, Sweden




No really. Just suddenly recall the keyword 'algorithm' but have to search by 'algo' due to poster misspelled it.


KH

Go to Top of Page

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/22/2007 :  01:32:55  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote
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~~~
Go to Top of Page

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/22/2007 :  01:39:12  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote
oh mann.. this will take sometime to study .. dont even know where to start!!

~~~Focus on problem, not solution~~~
Go to Top of Page

khtan
In (Som, Ni, Yak)

Singapore
17681 Posts

Posted - 02/22/2007 :  01:41:07  Show Profile  Reply with Quote
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~~~


Don't forget to thank Peter for the algorithm


KH

Go to Top of Page

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/22/2007 :  02:16:20  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote
yup.. ive run the thing.. wow.. unbelieveable... i could just call it in my Sp.. tq.. really good thing peter!

~~~Focus on problem, not solution~~~
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30281 Posts

Posted - 02/22/2007 :  02:19:32  Show Profile  Visit SwePeso's Homepage  Reply with Quote
You're welcome!


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/22/2007 :  02:23:11  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote
wait,(maybe this quite silly Q :( ! ) how to customade the table we use.. in my case, i want to use tblitemdetail and compare the originqty column.. doo i have to change something in the function or what> pliz help.. thanks a lot

~~~Focus on problem, not solution~~~
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30281 Posts

Posted - 02/22/2007 :  02:30:31  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Yes, you have to change the INSERT statement to the @Stage table variable, ie change the source of the insert, and the column names fro the INSERT for the source columns.


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/22/2007 :  02:59:10  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote
peter,

ive try to customade the insert variables :-

-- Stage the data
DECLARE @Stage TABLE (RowID INT IDENTITY(0, 1), Number MONEY, UniqueID VARCHAR(12))

INSERT @Stage
(
Number,
UniqueID
)
SELECT OriginQty AS Number,
ItemStorageID AS UniqueID
FROM [tblItemDetail] where itemid='Flower'

i)in my tblitemdetail, my originqty is in float type, is that ok?
ii) this table also have many records to filter around 30k and above, until now, it is still processing my request(>5 mins) :-

select * FROm fnGetAnyCombination(30)

is this normal? or maybe i misunderstanding anything.. thanks

~~~Focus on problem, not solution~~~
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30281 Posts

Posted - 02/22/2007 :  03:12:48  Show Profile  Visit SwePeso's Homepage  Reply with Quote
You have 30k records to insert into the @stage table?
That is ok, but remember that the number of permutations are 2^30 to check later.
That is somewhat equal to 1 000 000 000 combinations to check. That could take a while...

How many unique combinations for OriginQty and ItemStorageID do you have? If there are a lot of duplicates, only insert distinct values.
Also, you could try the improved version posted later in the topic linked above!
If all OriginQty are positive, there is an speed improvement for the function.


How many uniqu values for

Peter Larsson
Helsingborg, Sweden
Go to Top of Page

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/22/2007 :  03:24:21  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote

yup, my itemstorageid is unique, exists only once in a tbl..
umm... is it correct if i add restiction in the function insert statement, in my tblitemdetail like

SELECT OriginQty ,ItemStorageID
FROM [tblItemDetail] where itemid='Flower'

okay, suppose this normal statement will produce only 40 rows.. but when applying to the function until now it still processing the function.. that is too slow.. something i did wrong or what?

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

Edited by - maya_zakry on 02/22/2007 03:32:17
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30281 Posts

Posted - 02/22/2007 :  03:36:26  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Do you really need all the combinations possible? or is the first combination enough?
Use the last version of the function in the link above.

SELECT * FROM dbo.fnGetAnyCombination(30, 1, 0)


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 02/22/2007 03:41:51
Go to Top of Page

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/22/2007 :  03:43:14  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote
the first and closest combination is enuff.. okay ill try that new version first..
and also, i try on the smaller table size.. around 30-40 records... and still it's too slow.. am i on track .. uwwawawawwawawaaaaaaaaaaaa

and unfortunately, my originqty is not uniueq, only itemstorageid, itemstorageid : A1,A2,A3 could have same originqty

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

Edited by - maya_zakry on 02/22/2007 03:46:24
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30281 Posts

Posted - 02/22/2007 :  03:49:39  Show Profile  Visit SwePeso's Homepage  Reply with Quote
The drawback feature with the function is that it brute-force tests all combinations!
There are other ways to go, if you only want the closest sum, or the first sum found...


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30281 Posts

Posted - 02/22/2007 :  03:51:56  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Post the 30-40 records you have, and your expected output of them, and I will try to write some new algorithm to fetch them.


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

maya_zakry
Constraint Violating Yak Guru

Malaysia
379 Posts

Posted - 02/22/2007 :  04:08:58  Show Profile  Click to see maya_zakry's MSN Messenger address  Send maya_zakry a Yahoo! Message  Reply with Quote
ItemStorageID OriginQty
IS0607523 899
IS0607526 100
IS0607725 95
IS0607730 50
IS0607731 55
IS0607732 40
IS0607733 5
IS0607981 100
IS0607982 100
IS0607983 100
IS0607984 100
IS0607985 100
IS0607986 50
IS0607990 250
IS0607991 100
IS0608003 100
IS0608004 100
IS0608005 100
IS0608006 100
IS0608007 100
IS0608008 100
IS0608010 100
IS0608011 100
IS0608014 90
IS0608034 100
IS0608035 100
IS0608036 100
IS0608037 100
IS0608038 100
IS0608039 100
IS0608046 50
IS0608047 350
IS0608833 450
IS0608834 450
IS0608835 100
IS0608840 100
IS0608842 50
IS0608843 50
IS0608f011 50
IS0609117 1
IS0609770 10
IS0609846 1

-first i dun know how ppl post records and output here in the forum.. for me, i paste in execl and repaste here...
-from the records,just wanna find the closest combination base on some restriction in my where statement(to consider many things lik,e expirydate, location) but for now, need to make this originqty combination up first..

~~~Focus on problem, not solution~~~
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30281 Posts

Posted - 02/22/2007 :  06:05:22  Show Profile  Visit SwePeso's Homepage  Reply with Quote
With the test data above, try this! It takes me only 2 seconds the get the nearest match for the wanted sum 349!
-- 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

Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 02/22/2007 08:58:59
Go to Top of Page
Page: of 2 Previous Topic Topic Next Topic  
Next Page
 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.3 seconds. Powered By: Snitz Forums 2000