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
 query challenge
 New Topic  Reply to Topic
 Printer Friendly
Previous Page
Author Previous Topic Topic Next Topic
Page: of 2

SwePeso
Patron Saint of Lost Yaks

Sweden
30188 Posts

Posted - 07/21/2013 :  02:53:20  Show Profile  Visit SwePeso's Homepage  Reply with Quote
This problem is known as "bin packaging" and I have a very fast implementation here
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=80857



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA
Go to Top of Page

LoztInSpace
Aged Yak Warrior

940 Posts

Posted - 07/22/2013 :  08:54:29  Show Profile  Reply with Quote
Hi again,
Seems like you've worked it out so I won't explain how it works. Peso has provided another version for you to try so hopefully you're on your way.

I overlooked the requirement for 100 outstanding invoices so probably my solution is not so good. The problem space on this is massive (1267650600228229401496703205376 combinations!) so you're not going to be able to solve this with any certainty without some cleverer maths than I am able to come up with.

One interesting approach I did think of was that by using the least significant digit of each invoice you might be able to use the same algorithm to narrow the eligible invoices.
Say for example your received payment ends in 3. Only certain combinations of last digit totals will result in that.
Initially run the algorithm across 0....9 instead of all your invoices. Only certain combinations will actually result in a number ending with 3. You can then only include the invoices that end with the digits in the combinations that result.
I'm not entirely sure if that will exclude enough or even work but hope to try it if I get a chance. Even if it does work it could still leave you with an unfeasible problem space (e.g. if you have a payment of xxxx3, one invoice of yyyy3 and 99 invoices of zzzzz0 you still can't get a sensible reduction in combinations as you'd still need to consider all the zzz0s). Perhaps some iterative/recursiveness would help but like I said, not sure even if that refinement works.
Maybe just try Peso's approach :)
Good luck
Go to Top of Page

barnabeck
Posting Yak Master

Spain
190 Posts

Posted - 07/22/2013 :  18:07:21  Show Profile  Reply with Quote
@LoztInSpace: this is getting so complex... I hardly can imagine taking advantage of anything regarding the last digits, as any digit comes up with the same probability. I was so overwhelmed by the simplicity of my loop and about the way of taking advantage of the resemblance of the number in binary - something that nobody actually commented :( .... but in the end its far to slow and Peso on the other hand has a very fast implementation, that found the right combination for 30 invoices in a few seconds, so there's little doubt about what suits me best.

@Peso: your algorithm is really fast and so I spent some time, while I was waiting for my query to finish (I stopped it after 5 hours) to adapt it to my needs.
- I need all solutions
- No best approach needed
- I have 2 columns to be processed, along with the amount (qty) goes the invoice

Little by little I adapted parts of it, and it still worked until I finally took away that break command, on that the match-criteria-check and eliminated the closest approach bits; as I want the routine to look for just the hit solutions.
DECLARE	@WantedValue REAL

SET	@WantedValue = 3327.02

-- Stage the source data
DECLARE	@Data TABLE
	(
		RecID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
		MaxItems INT,
		Invoice NVARCHAR(12),
		CurrentItems INT DEFAULT 0,
		FaceValue REAL,
		BestUnder REAL DEFAULT 0,
		BestOver REAL DEFAULT 1
	)

-- Aggregate the source data
INSERT		@Data
		(	
			MaxItems,
			FaceValue,
			Invoice
		)
SELECT		COUNT(*),
		Qty, Invoice
FROM		(
SELECT 'SOI20002384' as Invoice, 354.00 as Qty UNION ALL
SELECT 'SOI30003969' as Invoice, 241.52 as Qty UNION ALL
SELECT 'SOI30004521' as Invoice, 1207.58 as Qty UNION ALL
SELECT 'SOI30004535' as Invoice, 1509.48 as Qty UNION ALL
SELECT 'SOI30004612' as Invoice, 2238.50 as Qty UNION ALL
SELECT 'SOI30004662' as Invoice, 2775.74 as Qty UNION ALL
SELECT 'SOI30004900' as Invoice, 3085.50 as Qty UNION ALL
SELECT 'SOI30004901' as Invoice, 551.28 as Qty
		) AS d
GROUP BY	Qty, Invoice
ORDER BY	Qty DESC

-- Declare some control variables
DECLARE	@CurrentSum REAL,
	@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	Invoice 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
			SELECT	Invoice, FaceValue
			FROM	@Data
			WHERE	CurrentItems > 0
	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	Invoice,
		FaceValue
		FROM	@Data
		WHERE	BestUnder > 0
	ELSE
		-- If BestOver is closer to the sum we want, choose that
		SELECT	Invoice,
		FaceValue
		FROM	@Data
		WHERE	BestOver > 0
ELSE
	-- We have an exact match
	SELECT	Invoice,
		FaceValue
	FROM	@Data
	WHERE	CurrentItems > 0
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30188 Posts

Posted - 07/22/2013 :  19:33:40  Show Profile  Visit SwePeso's Homepage  Reply with Quote
You can strip the solution even more.
SET NOCOUNT ON;

DECLARE	@WantedValue MONEY = 3327.02;

DECLARE	@Data TABLE
	(
		ID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
		Invoice CHAR(11) NOT NULL,
		Amount MONEY NOT NULL,
		Items INT NOT NULL
	)

INSERT		@Data
		(	
			Invoice,
			Amount,
			Items
		)
SELECT		Invoice,
		Amount,
		Items
FROM		(
			VALUES		('SOI20002384',  354.00, 0),
					('SOI30003969',  241.52, 0),
					('SOI30004521', 1207.58, 0),
					('SOI30004535', 1509.48, 0),
					('SOI30004612', 2238.50, 0),
					('SOI30004662', 2775.74, 0),
					('SOI30004900', 3085.50, 0),
					('SOI30004901',  551.28, 0)
		) AS d(Invoice, Amount, Items)
WHERE		Amount <= @WantedValue
ORDER BY	Amount DESC;

DECLARE	@Sum MONEY = 0,
	@ID INT = 1;

WHILE @ID IS NOT NULL
	BEGIN
		UPDATE	@Data
		SET	Items =	CASE
					WHEN ID < @ID THEN 0
					ELSE 1
				END
		WHERE	ID <= @ID;

		SELECT	@Sum = SUM(Amount)
		FROM	@Data
		WHERE	Items = 1;

		IF @Sum = @WantedValue
			SELECT		Invoice,
					Amount
			FROM		@Data
			WHERE		Items = 1
			ORDER BY	Invoice;

		SELECT	@ID = MIN(ID)
		FROM	@Data
		WHERE	Items = 0;
	END



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA
Go to Top of Page

LoztInSpace
Aged Yak Warrior

940 Posts

Posted - 07/22/2013 :  19:53:42  Show Profile  Reply with Quote
Hi Barnabec,
I think there's some merit in my last digit but I'm not going to pursue it a) as you've found the solution, b) it may not actually limit the problem suffiently and c) I'm not really good enough at maths.

The reason I didn't comment on your binary solution is that I think it's the same algorithm as my query but more a more complicated implementation. It also shares the same problem space limitations (or rather lack of limitations).

Go to Top of Page

sigmas
Posting Yak Master

Belarus
172 Posts

Posted - 07/22/2013 :  20:42:22  Show Profile  Reply with Quote
quote:
Originally posted by SwePeso

You can strip the solution even more.
SET NOCOUNT ON;

DECLARE	@WantedValue MONEY = 3327.02;

DECLARE	@Data TABLE
	(
		ID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
		Invoice CHAR(11) NOT NULL,
		Amount MONEY NOT NULL,
		Items INT NOT NULL
	)

INSERT		@Data
		(	
			Invoice,
			Amount,
			Items
		)
SELECT		Invoice,
		Amount,
		Items
FROM		(
			VALUES		('SOI20002384',  354.00, 0),
					('SOI30003969',  241.52, 0),
					('SOI30004521', 1207.58, 0),
					('SOI30004535', 1509.48, 0),
					('SOI30004612', 2238.50, 0),
					('SOI30004662', 2775.74, 0),
					('SOI30004900', 3085.50, 0),
					('SOI30004901',  551.28, 0)
		) AS d(Invoice, Amount, Items)
WHERE		Amount <= @WantedValue
ORDER BY	Amount DESC;

DECLARE	@Sum MONEY = 0,
	@ID INT = 1;

WHILE @ID IS NOT NULL
	BEGIN
		UPDATE	@Data
		SET	Items =	CASE
					WHEN ID < @ID THEN 0
					ELSE 1
				END
		WHERE	ID <= @ID;

		SELECT	@Sum = SUM(Amount)
		FROM	@Data
		WHERE	Items = 1;

		IF @Sum = @WantedValue
			SELECT		Invoice,
					Amount
			FROM		@Data
			WHERE		Items = 1
			ORDER BY	Invoice;

		SELECT	@ID = MIN(ID)
		FROM	@Data
		WHERE	Items = 0;
	END



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA


How much time is required to process the query to 64 rows and trying to get a result?

(thinking) Executing query... After 30 minute...

Database Development MCTS, MCTIP

Edited by - sigmas on 07/22/2013 20:56:05
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30188 Posts

Posted - 07/22/2013 :  21:02:29  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Yes, bin-packaging is a np-problem.



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA
Go to Top of Page

sigmas
Posting Yak Master

Belarus
172 Posts

Posted - 07/22/2013 :  21:09:50  Show Profile  Reply with Quote
quote:
Originally posted by SwePeso

Yes, bin-packaging is a np-problem.



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA


You mean bin-packing, right?

Database Development MCTS, MCTIP
Go to Top of Page

LoztInSpace
Aged Yak Warrior

940 Posts

Posted - 07/22/2013 :  22:29:55  Show Profile  Reply with Quote
quote:
Originally posted by barnabeck
- I need all solutions


Then I am afraid you must resign yourself to failure. As I said - the combinations of 100 invoices is too large. Even 30 invoices has over a billion combinations to check. The best you can do is apply some heuristics (or ask your customers to specifiy what it is they are paying for).

I think this is the reason people run accounts. Maybe it's time to adopt that approach!
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30188 Posts

Posted - 07/23/2013 :  03:39:59  Show Profile  Visit SwePeso's Homepage  Reply with Quote
If one invoice can be used for multiple solutions, do you want all solutions for that invoice, or just the first one?
If you only want one solution for an invoice, we can cut time significantly.



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30188 Posts

Posted - 07/23/2013 :  03:48:45  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Try this. For every hit, it reduces the number of permutations by 2^(number of invoices for solution).
SET NOCOUNT ON;

DECLARE	@WantedValue MONEY = 3327.02;

DECLARE	@Data TABLE
	(
		ID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
		Invoice CHAR(11) NOT NULL,
		Amount MONEY NOT NULL,
		Items INT NOT NULL
	)

INSERT		@Data
		(	
			Invoice,
			Amount,
			Items
		)
SELECT		Invoice,
		Amount,
		Items
FROM		(
			VALUES		('SOI20002384',  354.00, 0),
					('SOI30003969',  241.52, 0),
					('SOI30004521', 1207.58, 0),
					('SOI30004535', 1509.48, 0),
					('SOI30004612', 2238.50, 0),
					('SOI30004662', 2775.74, 0),
					('SOI30004900', 3085.50, 0),
					('SOI30004901',  551.28, 0)
		) AS d(Invoice, Amount, Items)
WHERE		Amount <= @WantedValue
ORDER BY	Amount DESC;

DECLARE	@Solutions TABLE
	(
		Solution INT NOT NULL,
		Invoice CHAR(11) NOT NULL,
		PRIMARY KEY CLUSTERED
		(
			Solution,
			Invoice
		),
		Amount MONEY NOT NULL
	);

DECLARE	@Sum MONEY = 0,
	@ID INT = 1,
	@Solution INT = 1;

WHILE @ID IS NOT NULL
	BEGIN
		UPDATE	@Data
		SET	Items =	CASE
					WHEN ID < @ID THEN 0
					ELSE 1
				END
		WHERE	ID <= @ID;

		SELECT	@Sum = SUM(Amount)
		FROM	@Data
		WHERE	Items = 1;

		IF @Sum = @WantedValue
			BEGIN
				INSERT	@Solutions
					(
						Solution,
						Invoice,
						Amount
					)
				SELECT	@Solution,
					Invoice,
					Amount
				FROM	@Data
				WHERE	Items = 1;

				MERGE	@Data AS tgt
				USING	(
						SELECT	Invoice
						FROM	@Solutions
						WHERE	Solution = @Solution
					) AS src ON src.Invoice = tgt.Invoice
				WHEN	MATCHED
						THEN	DELETE
				WHEN	NOT MATCHED BY SOURCE
						THEN	UPDATE
							SET	Items = 0;

				SET	@Solution += 1;
			END

		SELECT	@ID = MIN(ID)
		FROM	@Data
		WHERE	Items = 0;
	END

SELECT	Solution,
	Invoice,
	Amount
FROM	@Solutions;



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA
Go to Top of Page

barnabeck
Posting Yak Master

Spain
190 Posts

Posted - 07/24/2013 :  04:29:27  Show Profile  Reply with Quote
Thank you Peso for adapting the algorithm to my needs. I'm busy in a workshop that's why I wasn't commenting any of the postings.

Actually I don't need all solutions... I just need one single solution and prove that this is the only existing one! If there are more solutions we have to contact the customer anyway and go through a different procedure.

The last solution Peso posted took 3 hours to be executed...
Martin
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30188 Posts

Posted - 07/24/2013 :  04:52:10  Show Profile  Visit SwePeso's Homepage  Reply with Quote
How long does it take if you comment out the MERGE statement?



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA
Go to Top of Page

LoztInSpace
Aged Yak Warrior

940 Posts

Posted - 07/24/2013 :  08:02:13  Show Profile  Reply with Quote
Guys,
You need to work out all combinations to a) firmly establish that there is only one solution or b) there is more than one (by extension of a) but at least you might be able to short circuit that
It will take until the heat death of the universe to achieve a) though hopefully b) can be achieved quicker, there are no promises. You might find the last combination is the one you need.
Martin - you need to understand this - unless there are constraints you have not told us about, your mission is futile!
Sorry, mate. That's just maths. Get your clients to work off an account and just take the money received off the money owed irrespective of the individual invoices.
Go to Top of Page

barnabeck
Posting Yak Master

Spain
190 Posts

Posted - 07/25/2013 :  03:07:51  Show Profile  Reply with Quote
Peso: this last run, without the merge statement took 11 hours and brought up a second solution I wasn't aware of.

LoztInSpace: off course you are right with your comment. In case that all solutions or a clear statement on the non existence of a second solution is needed, than by logic there can't be any workaround for a complete scan process through all possible combinations.

Conclusion: the online tool we will be providing to accountancy can be only of reasonable help if the number of invoices is around 20. In all other cases they have to contact the customer and get the necessary information from him.

Thank you all guys for comments, proposals and solutions posted, I learned a lot from this.
Martin
Go to Top of Page
Page: of 2 Previous Topic Topic Next Topic  
Previous 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.19 seconds. Powered By: Snitz Forums 2000