# Thinking outside the box

Patron Saint of Lost Yaks

## Bin packaging

With respect to my old algorithm found here http://weblogs.sqlteam.com/peterl/archive/2008/08/12/How-to-sum-up-an-unknown-number-of-records.aspx which is about how to sum up an unknown number of items, I have come up with a new algorithm.

This new algorithm is about finding all possible sums and how many combinations you have of each sum.
Have fun!

DECLARE       @Data TABLE
(
faceValue MONEY,
maxItems INT,
permCount INT
)

INSERT        @Data
(
faceValue,
maxItems
)
SELECT        faceValue,
1 + COUNT(*)
FROM          (
SELECT 899 AS faceValue 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      faceValue

DECLARE       @comb INT

UPDATE @Data
SET    @comb = permCount = maxItems * COALESCE(@comb, 1)

SELECT        theSum,
COUNT(*) AS theCount
FROM          (
SELECT        SUM(d.faceValue *((v.number * d.maxItems / d.permCount) % d.maxItems)) AS theSum
FROM          @Data AS d
INNER JOIN    TallyNumbers AS v ON v.number <= @comb
GROUP BY      v.number
HAVING        SUM(d.faceValue *((v.number * d.maxItems / d.permCount) % d.maxItems)) > 0
) AS d
GROUP BY      theSum
ORDER BY      COUNT(*) DESC,
theSum

Now you can see for any possible sum how many combination you have to get that sum.
With the sample data provided above, you can see that you can get the sum of 2651 rupees in 966 different ways, but you can only get the sum of 1019 rupees in one way.

Print | posted on Sunday, November 23, 2008 3:32 PM | Filed Under [ SQL Server 2008 Algorithms SQL Server 2005 SQL Server 2000 ]

## #re: Bin packaging

I'm trying to figure out what you're doing here. I populate Tally Numbers with 1019 and 2651, the script returns

theSum theCount
--------------------- -----------
202.00 1
1821.00 1

I'm pretty sure I'm missing something.
2/25/2009 1:05 AM | Cameron
Comments have been closed on this topic.