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

Our new SQL Server Forums are live!
Come on over! We've restricted the ability to create new threads on these forums.

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

@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

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

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

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?

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!

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

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

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

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.

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