Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase 12»»

Create sum closest to an integer Expand / Collapse
Author
Message
Posted Tuesday, July 30, 2013 7:22 AM


SSC-Addicted

SSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-Addicted

Group: General Forum Members
Last Login: Friday, September 12, 2014 5:45 AM
Points: 411, Visits: 275
Hi,

I need to create a function that will check an int column from a table and has to generate the best combinations to create a sum closest to an integer given.

For example:
the integer given is 10
the int column will have the following records : 5,6,3,4,3.

The function should return:
5,4 and 6,3

Thank you for any help!
Post #1478990
Posted Tuesday, July 30, 2013 8:07 AM


SSChampion

SSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampion

Group: General Forum Members
Last Login: Today @ 9:55 AM
Points: 13,434, Visits: 12,298
What you are describing is classically known as the "Bin packing problem". It is very complicated to say the least. There is no easy way to do this and in t-sql it will most certainly be very slow.

https://en.wikipedia.org/wiki/Bin_packing_problem


_______________________________________________________________

Need help? Help us help you.

Read the article at http://www.sqlservercentral.com/articles/Best+Practices/61537/ for best practices on asking questions.

Need to split a string? Try Jeff Moden's splitter.

Cross Tabs and Pivots, Part 1 – Converting Rows to Columns
Cross Tabs and Pivots, Part 2 - Dynamic Cross Tabs
Understanding and Using APPLY (Part 1)
Understanding and Using APPLY (Part 2)
Post #1479020
Posted Tuesday, July 30, 2013 3:36 PM


SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Yesterday @ 4:57 AM
Points: 802, Visits: 717
SQL Server MVP Hugo Kornelis has written a couple of blog posts about bin packing, see http://sqlblog.com/blogs/hugo_kornelis/archive/tags/Bin+Packing/default.aspx

Erland Sommarskog, SQL Server MVP, www.sommarskog.se
Post #1479197
Posted Tuesday, July 30, 2013 7:12 PM


Hall of Fame

Hall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of Fame

Group: General Forum Members
Last Login: Yesterday @ 10:55 PM
Points: 3,648, Visits: 5,321
I love SQL bin-packing problems! Hate to disagree with you Sean but they don't need to be overly complicated.

Before I suggest a solution, shouldn't the answer be 4, 6 (=10?)

Here's one solution that might start to get a little slow if you have:
- lot's of integers in your table AND
- you want to consider solutions that sum more than 3, 4 or 5 of those.

DECLARE @t TABLE (strcol CHAR(3));
DECLARE @ValueOfInterest INT = 10;

INSERT INTO @t (strcol)
SELECT ' 5' UNION ALL SELECT ' 6' UNION ALL SELECT ' 3'
UNION ALL SELECT ' 4' UNION ALL SELECT ' 3';

-- Improved Combinations
;WITH UNIQUEnTuples (n, Tuples, ID, CSum) AS (
SELECT DISTINCT 1, CAST(strcol AS VARCHAR(8000)), strcol, CAST(strcol AS INT)
FROM @t
UNION ALL
SELECT 1 + n.n, t.strcol + ',' + n.Tuples, strcol, CSum+CAST(t.strcol AS INT)
FROM UNIQUEnTuples n
CROSS APPLY (
SELECT strcol
FROM @t t
WHERE t.strcol < n.ID) t
)
SELECT TOP 1 Tuples, SumOfTuples=CSum
FROM UNIQUEnTuples
WHERE n <= 2 AND CSum <= @ValueOfInterest
ORDER BY CSum DESC;


This is actually a slightly improved version of some code I submitted a couple of years back: Generating n-Tuples with SQL. The improved version appears towards the end of the discussion thread.

Note that the WHERE clause can be adjusted to account for the number of integers you want to sum and/or whether you allow the value to be within a plus or minus range, for example:

WHERE n <= 3 AND CSum BETWEEN @ValueOfInterest - 1 AND @ValueOfInterest + 1

Would give you up to 3 summed integers where the range is plus or minus 1 from your value of interest. Of course, you may want to select the TOP 5 in such a case and then later decide to narrow it down.

Edit: Note also that if the number of integers to sum is unbounded, meaning you don't care how many sum to meet your target, you should put a CSUM <= @ValueOfInterest WHERE clause in the recursive leg of the rCTE so that on the result that exceeds your target, all further combinations are avoided.



My mantra: No loops! No CURSORs! No RBAR! Hoo-uh!

My thought question: Have you ever been told that your query runs too fast?

My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.


Need to UNPIVOT? Why not CROSS APPLY VALUES instead?
Since random numbers are too important to be left to chance, let's generate some!
Learn to understand recursive CTEs by example.
Splitting strings based on patterns can be fast!
Post #1479250
Posted Tuesday, July 30, 2013 7:39 PM


Hall of Fame

Hall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of Fame

Group: General Forum Members
Last Login: Yesterday @ 10:55 PM
Points: 3,648, Visits: 5,321
Here's an example that processes 100 random integers up to 3-tuples with target value of 100. It takes less than 3 seconds to run on my box.

DECLARE @t TABLE (strcol CHAR(4));
DECLARE @ValueOfInterest INT = 100;

INSERT INTO @t (strcol)
--SELECT ' 5' UNION ALL SELECT ' 6' UNION ALL SELECT ' 3'
--UNION ALL SELECT ' 4' UNION ALL SELECT ' 3';
SELECT TOP 100 RIGHT('000' + CAST(ABS(CHECKSUM(NEWID())) % 200 AS VARCHAR(3)), 4)
FROM sys.all_columns;

SET STATISTICS TIME ON;
-- Improved Combinations
WITH UNIQUEnTuples (n, Tuples, ID, CSum) AS (
SELECT DISTINCT 1, CAST(strcol AS VARCHAR(8000)), strcol, CAST(strcol AS INT)
FROM @t
UNION ALL
SELECT 1 + n.n, t.strcol + ',' + n.Tuples, strcol, CSum+t.strcol
FROM UNIQUEnTuples n
CROSS APPLY (
SELECT strcol
FROM @t t
WHERE t.strcol < n.ID) t
WHERE CSum+t.strcol <= @ValueOfInterest
)
SELECT TOP 5 Tuples, SumOfTuples=CSum
FROM UNIQUEnTuples
WHERE n <= 3 AND CSum <= @ValueOfInterest
ORDER BY CSum DESC
OPTION (RECOMPILE);
SET STATISTICS TIME OFF;


Edit: Two notes (afterthoughts):
- I added OPTION(RECOMPILE) because it might help to eliminate parameter sniffing in case you run this many times on tables of different sizes.
- If you need to consider a solution (from your original problem) like 3+3, you need to remove the DISTINCT clause in the anchor leg of the query.



My mantra: No loops! No CURSORs! No RBAR! Hoo-uh!

My thought question: Have you ever been told that your query runs too fast?

My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.


Need to UNPIVOT? Why not CROSS APPLY VALUES instead?
Since random numbers are too important to be left to chance, let's generate some!
Learn to understand recursive CTEs by example.
Splitting strings based on patterns can be fast!
Post #1479252
Posted Wednesday, July 31, 2013 7:24 AM


SSChampion

SSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampion

Group: General Forum Members
Last Login: Today @ 9:55 AM
Points: 13,434, Visits: 12,298
dwain.c (7/30/2013)
I love SQL bin-packing problems! Hate to disagree with you Sean but they don't need to be overly complicated.

Before I suggest a solution, shouldn't the answer be 4, 6 (=10?)

Here's one solution that might start to get a little slow if you have:
- lot's of integers in your table AND
- you want to consider solutions that sum more than 3, 4 or 5 of those.

DECLARE @t TABLE (strcol CHAR(3));
DECLARE @ValueOfInterest INT = 10;

INSERT INTO @t (strcol)
SELECT ' 5' UNION ALL SELECT ' 6' UNION ALL SELECT ' 3'
UNION ALL SELECT ' 4' UNION ALL SELECT ' 3';

-- Improved Combinations
;WITH UNIQUEnTuples (n, Tuples, ID, CSum) AS (
SELECT DISTINCT 1, CAST(strcol AS VARCHAR(8000)), strcol, CAST(strcol AS INT)
FROM @t
UNION ALL
SELECT 1 + n.n, t.strcol + ',' + n.Tuples, strcol, CSum+CAST(t.strcol AS INT)
FROM UNIQUEnTuples n
CROSS APPLY (
SELECT strcol
FROM @t t
WHERE t.strcol < n.ID) t
)
SELECT TOP 1 Tuples, SumOfTuples=CSum
FROM UNIQUEnTuples
WHERE n <= 2 AND CSum <= @ValueOfInterest
ORDER BY CSum DESC;


This is actually a slightly improved version of some code I submitted a couple of years back: Generating n-Tuples with SQL. The improved version appears towards the end of the discussion thread.

Note that the WHERE clause can be adjusted to account for the number of integers you want to sum and/or whether you allow the value to be within a plus or minus range, for example:

WHERE n <= 3 AND CSum BETWEEN @ValueOfInterest - 1 AND @ValueOfInterest + 1

Would give you up to 3 summed integers where the range is plus or minus 1 from your value of interest. Of course, you may want to select the TOP 5 in such a case and then later decide to narrow it down.

Edit: Note also that if the number of integers to sum is unbounded, meaning you don't care how many sum to meet your target, you should put a CSUM <= @ValueOfInterest WHERE clause in the recursive leg of the rCTE so that on the result that exceeds your target, all further combinations are avoided.


Dwain this is pretty cool but it doesn't provide the results the OP was looking for. This only returns the one combination that most closely meets the @ValueOfInterest. The OP was looking to have all the values put into groups. The OP stated they wanted back 5,4 and 6,3. Now I agree that doesn't seem like the most logical thing and the second value of 3 went missing. I would think that 6,4 : 5,3 : 3 would be the best fit. I can't some up with a way to make your awesome example return the best fit of all the values.


_______________________________________________________________

Need help? Help us help you.

Read the article at http://www.sqlservercentral.com/articles/Best+Practices/61537/ for best practices on asking questions.

Need to split a string? Try Jeff Moden's splitter.

Cross Tabs and Pivots, Part 1 – Converting Rows to Columns
Cross Tabs and Pivots, Part 2 - Dynamic Cross Tabs
Understanding and Using APPLY (Part 1)
Understanding and Using APPLY (Part 2)
Post #1479472
Posted Wednesday, July 31, 2013 7:36 AM


Hall of Fame

Hall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of Fame

Group: General Forum Members
Last Login: Yesterday @ 10:55 PM
Points: 3,648, Visits: 5,321
Sean Lange (7/31/2013)
dwain.c (7/30/2013)
I love SQL bin-packing problems! Hate to disagree with you Sean but they don't need to be overly complicated.

Before I suggest a solution, shouldn't the answer be 4, 6 (=10?)

Here's one solution that might start to get a little slow if you have:
- lot's of integers in your table AND
- you want to consider solutions that sum more than 3, 4 or 5 of those.

DECLARE @t TABLE (strcol CHAR(3));
DECLARE @ValueOfInterest INT = 10;

INSERT INTO @t (strcol)
SELECT ' 5' UNION ALL SELECT ' 6' UNION ALL SELECT ' 3'
UNION ALL SELECT ' 4' UNION ALL SELECT ' 3';

-- Improved Combinations
;WITH UNIQUEnTuples (n, Tuples, ID, CSum) AS (
SELECT DISTINCT 1, CAST(strcol AS VARCHAR(8000)), strcol, CAST(strcol AS INT)
FROM @t
UNION ALL
SELECT 1 + n.n, t.strcol + ',' + n.Tuples, strcol, CSum+CAST(t.strcol AS INT)
FROM UNIQUEnTuples n
CROSS APPLY (
SELECT strcol
FROM @t t
WHERE t.strcol < n.ID) t
)
SELECT TOP 1 Tuples, SumOfTuples=CSum
FROM UNIQUEnTuples
WHERE n <= 2 AND CSum <= @ValueOfInterest
ORDER BY CSum DESC;


This is actually a slightly improved version of some code I submitted a couple of years back: Generating n-Tuples with SQL. The improved version appears towards the end of the discussion thread.

Note that the WHERE clause can be adjusted to account for the number of integers you want to sum and/or whether you allow the value to be within a plus or minus range, for example:

WHERE n <= 3 AND CSum BETWEEN @ValueOfInterest - 1 AND @ValueOfInterest + 1

Would give you up to 3 summed integers where the range is plus or minus 1 from your value of interest. Of course, you may want to select the TOP 5 in such a case and then later decide to narrow it down.

Edit: Note also that if the number of integers to sum is unbounded, meaning you don't care how many sum to meet your target, you should put a CSUM <= @ValueOfInterest WHERE clause in the recursive leg of the rCTE so that on the result that exceeds your target, all further combinations are avoided.


Dwain this is pretty cool but it doesn't provide the results the OP was looking for. This only returns the one combination that most closely meets the @ValueOfInterest. The OP was looking to have all the values put into groups. The OP stated they wanted back 5,4 and 6,3. Now I agree that doesn't seem like the most logical thing and the second value of 3 went missing. I would think that 6,4 : 5,3 : 3 would be the best fit. I can't some up with a way to make your awesome example return the best fit of all the values.


I agree that clarification is needed on what is meant by "best fit." That's why I asked if 4,6 shouldn't be the correct answer and offered some suggestions to modify the WHERE clause to address whatever that requirement is.

Then there's also the question of whether 3,3,4 is one of the "best fit" solutions needed.



My mantra: No loops! No CURSORs! No RBAR! Hoo-uh!

My thought question: Have you ever been told that your query runs too fast?

My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.


Need to UNPIVOT? Why not CROSS APPLY VALUES instead?
Since random numbers are too important to be left to chance, let's generate some!
Learn to understand recursive CTEs by example.
Splitting strings based on patterns can be fast!
Post #1479481
Posted Wednesday, July 31, 2013 7:49 AM


SSChampion

SSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampion

Group: General Forum Members
Last Login: Today @ 9:55 AM
Points: 13,434, Visits: 12,298
dwain.c (7/31/2013)


I agree that clarification is needed on what is meant by "best fit." That's why I asked if 4,6 shouldn't be the correct answer and offered some suggestions to modify the WHERE clause to address whatever that requirement is.

Then there's also the question of whether 3,3,4 is one of the "best fit" solutions needed.


And this is why I said this can get really complicated. Maybe the rule is to get the best fit (least number of bins) and always fill them as full as possible. If that were the case then 4,3,3 : 5 : 6 would be the best fit. The debate goes on and on and on...


_______________________________________________________________

Need help? Help us help you.

Read the article at http://www.sqlservercentral.com/articles/Best+Practices/61537/ for best practices on asking questions.

Need to split a string? Try Jeff Moden's splitter.

Cross Tabs and Pivots, Part 1 – Converting Rows to Columns
Cross Tabs and Pivots, Part 2 - Dynamic Cross Tabs
Understanding and Using APPLY (Part 1)
Understanding and Using APPLY (Part 2)
Post #1479494
Posted Wednesday, July 31, 2013 7:56 AM
SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Today @ 10:03 AM
Points: 2,848, Visits: 5,094
Slightly modified Dwain code to return exactly what OP has asked:
DECLARE @t TABLE (strcol CHAR(3));
DECLARE @ValueOfInterest INT = 10;

INSERT INTO @t (strcol)
SELECT ' 5' UNION ALL SELECT ' 6' UNION ALL SELECT ' 3'
UNION ALL SELECT ' 4' UNION ALL SELECT ' 3';

-- Improved Combinations
;WITH UNIQUEnTuples (n, Tuples, ID, CSum) AS (
SELECT DISTINCT 1, CAST(strcol AS VARCHAR(8000)), strcol, CAST(strcol AS INT)
FROM @t
UNION ALL
SELECT 1 + n.n, t.strcol + ',' + n.Tuples, strcol, CSum+CAST(t.strcol AS INT)
FROM UNIQUEnTuples n
CROSS APPLY (
SELECT strcol
FROM @t t
WHERE t.strcol < n.ID) t
)
SELECT DISTINCT Tuples, SumOfTuples=CSum
FROM UNIQUEnTuples
WHERE n <= 2 AND CSum = (SELECT MAX(CSum) MS
FROM UNIQUEnTuples
WHERE n <= 2 AND CSum < @ValueOfInterest)
ORDER BY CSum DESC;



_____________________________________________
"The only true wisdom is in knowing you know nothing"
"O skol'ko nam otkrytiy chudnyh prevnosit microsofta duh!"
(So many miracle inventions provided by MS to us...)

How to post your question to get the best and quick help
Post #1479499
Posted Wednesday, July 31, 2013 8:13 AM


SSC-Addicted

SSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-Addicted

Group: General Forum Members
Last Login: Friday, September 12, 2014 5:45 AM
Points: 411, Visits: 275
Thank you very much for all your replies!

You were right about the rule to get the best fit and always fill the batches as full as possible. I am so sorry for not giving the correct specifications sooner on this issue.

But, thank you again on all your replies!
Post #1479504
« Prev Topic | Next Topic »

Add to briefcase 12»»

Permissions Expand / Collapse